\documentclass[preprint]{sigplanconf}

\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{breakurl}             % Not needed if you use pdflatex only.
\usepackage{color}
\usepackage{epsfig}
\usepackage{esvect}
\usepackage{listings}
\usepackage{mathpartir}
\usepackage{MnSymbol}
\usepackage{multirow}
\usepackage{rotating}

\lstdefinestyle{Caml}{language=Caml,%
  literate={when}{{{\bf when}}}4
}

\lstdefinestyle{C++}{language=C++,%
showstringspaces=false,
  columns=fullflexible,
  escapechar=@,
  basicstyle=\sffamily,
%  commentstyle=\rmfamily\itshape,
  moredelim=**[is][\color{white}]{~}{~},
  literate={[<]}{{\textless}}1      {[>]}{{\textgreater}}1 %
           {<}{{$\langle$}}1        {>}{{$\rangle$}}1 %
           {<=}{{$\leq$}}1          {>=}{{$\geq$}}1          
           {==}{{$==$}}2            {!=}{{$\neq$}}1 %
           {=>}{{$\Rightarrow\;$}}1 {->}{{$\rightarrow{}$}}1 %
           {<:}{{$\subtype{}\ $}}1  {<-}{{$\leftarrow$}}1 %
           {e1}{{$e_1$}}2 {e2}{{$e_2$}}2 {e3}{{$e_3$}}2 {e4}{{$e_4$}}2%
           {E1}{{$E_1$}}2 {E2}{{$E_2$}}2 {E3}{{$E_3$}}2 {E4}{{$E_4$}}2%
           {m_e1}{{$m\_e_1$}}4 {m_e2}{{$m\_e_2$}}4 {m_e3}{{$m\_e_3$}}4 {m_e4}{{$m\_e_4$}}4%
           {Match}{{\emph{Match}}}5 %
           {Case}{{\emph{Case}}}4 %
           {Qua}{{\emph{Qua}}}3 %
           {Otherwise}{{\emph{Otherwise}}}9 %
           {EndMatch}{{\emph{EndMatch}}}8 %
           {CM}{{\emph{CM}}}2 {KS}{{\emph{KS}}}2 {KV}{{\emph{KV}}}2 
}
\lstset{style=C++}
\DeclareRobustCommand{\code}[1]{{\lstinline[breaklines=false,escapechar=@]{#1}}}
\DeclareRobustCommand{\codehaskell}[1]{{\lstinline[breaklines=false,language=Haskell]{#1}}}
\DeclareRobustCommand{\codeocaml}[1]{{\lstinline[breaklines=false,language=Caml]{#1}}}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}

%% grammar commands
\newcommand{\Rule}[1]{{\rmfamily\itshape{#1}}}
\newcommand{\Alt}{\ensuremath{|}}
\newcommand{\is}{$::=$}
\newcommand{\subtype}{\textless:}
\newcommand{\evals}{\Rightarrow}
\newcommand{\evalspp}{\Rightarrow^+}
\newcommand{\DynCast}[2]{\ensuremath{dc\langle{#1}\rangle({#2})}}
\newcommand{\nullptr}{\ensuremath{\bot}}

\newcommand{\f}[1]{{ {\bf \textcolor{blue}{#1\%}}}}
\newcommand{\s}[1]{{ {\em \textcolor{cyan}{#1\%}}}}
\newcommand{\n}[1]{{ {\bf ~ ~ ~ ~ }}}
\newcommand{\Opn}{{\scriptsize {\bf Open}}}
\newcommand{\Cls}{{\scriptsize {\bf Tag}}}
\newcommand{\Unn}{{\scriptsize {\bf Union}}}

\input{data2}

\newsavebox{\sembox}
\newlength{\semwidth}
\newlength{\boxwidth}

\newcommand{\Sem}[1]{%
\sbox{\sembox}{\ensuremath{#1}}%
\settowidth{\semwidth}{\usebox{\sembox}}%
\sbox{\sembox}{\ensuremath{\left[\usebox{\sembox}\right]}}%
\settowidth{\boxwidth}{\usebox{\sembox}}%
\addtolength{\boxwidth}{-\semwidth}%
\left[\hspace{-0.3\boxwidth}%
\usebox{\sembox}%
\hspace{-0.3\boxwidth}\right]%
}

\newcommand{\authormodification}[2]{{\color{#1}#2}}
\newcommand{\ys}[1]{\authormodification{blue}{#1}}
\newcommand{\bs}[1]{\authormodification{red}{#1}}
\newcommand{\gdr}[1]{\authormodification{magenta}{#1}}

\begin{document}

%\conferenceinfo{PLDI 2012}{Beijing, China} 
%\copyrightyear{2012} 
%\copyrightdata{[to be supplied]} 

\titlebanner{Draft}        % These are ignored unless
\preprintfooter{Y.Solodkyy, G.Dos Reis, B.Stroustrup: Pattern Matching for C++}   % 'preprint' option specified.

\title{An elegant and efficient pattern matching library for C++}
%\subtitle{your \code{visit}, Jim, is not \code{accept}able anymore}
%\subtitle{\code{accepting} aint no \code{visit}ors}

\authorinfo{Yuriy Solodkyy\and Gabriel Dos Reis\and Bjarne Stroustrup}
           {Texas A\&M University\\ Texas, USA}
           {\{yuriys,gdr,bs\}@cse.tamu.edu}

\maketitle

\begin{abstract}
Pattern matching is an abstraction mechanism that greatly simplifies code. We 
present functional-programming-style pattern matching for C++ implemented as a 
library. The library provides a uniform notation for matching against different 
encodings of algebraic as well as extensible hierarchical data types in C++. The 
library integrates well with programming styles supported by C++ and can be used 
in the presense of multiple inheritance as well as in generic code.

We demonstrate that most of the traditional patterns seen in functional 
languages, can be made available in a language as library entities. This 
includes such demanded feature as views, as well as such controversial feature 
as n+k patterns. On one side, our library approach to pattern matching limits 
the amount of optimizations a compiler can perform on a pattern-matching code, 
but on the other hand it opens a whole new field for pattern matching 
optimizations with compile-time meta-programs. Besides, implementing pattern 
matching as a library allows us to experiment with syntax, implementation 
algorithms, and use while preserving benefit from the performance and 
portability provided by industrial compilers and support tools.

The library was originally motivated by and is used for applications involving 
large, typed, abstract syntax trees. By rewriting some of such applications we 
noted that the code written using our patterns is significantly more concise and 
easier to teach and comprehend than alternative solutions in C++. In particular, 
in scenarios typically approached with visitor design pattern, our 
pattern-matching solution better addresses more problems than the visitor design
pattern does: it is non-intrusive and does not have extensibility restrictions. 
It also avoids control inversion and can be used in pattern-matching scenarios 
that visitors are ill suited for.
\end{abstract}

\category{CR-number}{subcategory}{third-level}

\terms
Languages, Design

\keywords
Pattern Matching, Visitor Design Pattern, Expression Problem, C++

\section{Introduction} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:intro}

%Motivate the problem
%Give a summary of the paper: what you did and how
%Explicitly state your contribution

Pattern matching is an abstraction supported by many programming languages.
It allows the user tersely to describe a (possibly infinite) set of 
values accepted by the pattern. A \emph{pattern} represents a predicate on 
values, and is usually  much more concise and readable than the 
equivalent predicate spelled out as imperative code.

Popularized by functional programming community, most notably Hope\cite{BMS80}, 
ML\cite{ML90}, Miranda\cite{Miranda85} and Haskell\cite{Haskell98Book}, for 
providing syntax very close to mathematical notations, pattern matching has 
found its way into many imperative programming languages e.g. 
Pizza\cite{Odersky97pizzainto}, Scala\cite{Scala2nd}, Fortress\cite{RPS10}, as 
well as dialects of Java\cite{Liu03jmatch:iterable,HydroJ2003}, C++\cite{Prop96}, 
Eiffel\cite{Moreau:2003} and others. It is relatively easy to provide pattern 
matching when designing a new language, but to introduce it into a language in 
widespread use is a challenge. The obvious utility of the feature may be 
compromised by the need to fit into the language's syntax, semantics, and tool 
chains. A prototype implementation requires more effort than for an experimental 
language and is harder to get into use because mainstream users are unwilling 
to try non-portable, non-standard, unoptimized features.

To balance the utility and effort we decided to take the Semantically 
Enhanced Library Language (SELL) approach\cite{SELL}. We provide the
general-purpose programming language with a library, extended with a tool 
support. This will typically (as in this case) not provide you 100\% of the functionality that a 
language extension would do, but it allows experimentation and special-purpose use
with existing compilers and tool chains. With pattern matching, we managed to avoid 
external tool support by relying on some pretty nasty macro hacking to provide a
conventional and convenient interface to our efficient library implementation.

Our current solution is a proof of concept that sets a minimum threshold for 
performance, brevity, clarity and usefulness of a language solution for pattern 
matching in C++. It provides full functionality, so we can experiment with use 
of pattern matching in C++ and with language alternatives. To give an idea of 
what our library offers, consider an example from a domain where pattern matching 
is considered to provide terseness and clarity -- compiler construction. Imagine 
a simple language of expressions:

\begin{lstlisting}
@$exp$ \is{} $val$ \Alt{} $exp+exp$ \Alt{} $exp-exp$ \Alt{} $exp*exp$ \Alt{} $exp/exp$@
\end{lstlisting}

OCaml data type describing this grammar as well as simple evaluator of expressions 
in it can be declared as following:

\begin{lstlisting}[language=Caml,keepspaces,columns=flexible]
type expr = Value  of int
          | Plus   of expr * expr
          | Minus  of expr * expr
          | Times  of expr * expr
          | Divide of expr * expr
          ;;

let rec eval e =
  match e with
            Value  v      -> v
          | Plus   (a, b) -> (eval a) + (eval b)
          | Minus  (a, b) -> (eval a) - (eval b)
          | Times  (a, b) -> (eval a) * (eval b)
          | Divide (a, b) -> (eval a) / (eval b)
          ;;
\end{lstlisting}

The corresponding C++ data types would most likely be parameterized, but for
now we will just use simple classes:

\begin{lstlisting}[keepspaces,columns=flexible]
struct Expr { virtual @$\sim$@Expr() {} };
struct Value  : Expr { int value; };
struct Plus   : Expr { Expr* exp1; Expr* exp2; };
struct Minus  : Expr { Expr* exp1; Expr* exp2; };
struct Times  : Expr { Expr* exp1; Expr* exp2; };
struct Divide : Expr { Expr* exp1; Expr* exp2; };
\end{lstlisting}

Using our library, we can express matching about as tersely as OCaml:

\begin{lstlisting}[keepspaces,columns=flexible]
int eval(const Expr* e)
{
    Match(e)
    {
      Case(Value,  n)    return n;
      Case(Plus,   a, b) return eval(a) + eval(b);
      Case(Minus,  a, b) return eval(a) - eval(b);
      Case(Times,  a, b) return eval(a) * eval(b);
      Case(Divide, a, b) return eval(a) / eval(b);
    }
    EndMatch
}
\end{lstlisting}

To make the example fully functional we need to provide mappings of binding 
positions to corresponding class members:

\begin{lstlisting}[keepspaces,columns=flexible]
template <> struct bindings<Value>  { CM(0,Value::value); };
template <> struct bindings<Plus>   { CM(0,Plus::exp1); 
  ...                                 CM(1,Plus::exp2);   };
template <> struct bindings<Divide> { CM(0,Divide::exp1); 
                                      CM(1,Divide::exp2); };
\end{lstlisting}

This binding code would be implicitly provided by the compiler had
we chosen that implementation strategy.

The syntax is provided without any external tool support.
Instead we rely on a few C++0x 
features\cite{C++0x}, template meta-programming, and macros. As
shown in section~\ref{sec:eval}, it runs about as fast as the O'Caml version
and up to 80\% faster (depending on the usage 
scenario, compiler and underlain hardware) than a hand-crafted C++ code crafted using the 
\emph{Visitor Design Pattern}.

\subsection{Motivation}

%\subsection{Excursus}

The ideas and the library presented here were motivated by our rather 
unsatisfactory experiences working with various C++ front-ends and program 
analysis frameworks developed in C++\cite{Pivot09,Phoenix,Clang,Lise}. The 
problem was not in the frameworks per se, but in the fact that we had to use 
\emph{Visitor Design Pattern}\cite{DesignPatterns1993} to inspect, traverse and 
elaborate abstract syntax trees of their target languages. We found 
visitors unsuitable to express our application logic, and slow. 
We found dynamic casts in many places, often nested, because users
wanted to answer simple 
structural questions without having to resort to visitors.
Users preferred shorter, cleaner and a more direct code to visitors,
even at a high cost in performance (asuming that the programmer knew the cost).
The usage of \code{dynamic\_cast} resembled the use of 
pattern matching in functional languages to unpack algebraic data types. 
Thus, our initial goal was to develop a 
domain-specific library for C++ to express various 
predicates on tree-like structures as elegantly as functional languages.
This grew into a general high-performance pattern matching library.

The library presented here is the latest in a series of 5 libraries. The earlier 
versions were superceded because they failed to meet our standards for notation, 
performance, or generality. Our standard is set by the principle that a fair 
comparison must be against the gold standard in a field. For example, if we work 
on a linear algebra library, we must compare to Fortran or one of the industrial 
C++ libraries, rather than Java or C. For pattern matching we chose optimized 
O'Caml as our standard for closed (compile-time polymorphic) sets of classes and 
C++ for uses of the visitor pattern. For generality and simplicity of use, we 
deemed it essential to do both with a uniform syntax.

\subsection{Expression Problem}
\label{sec:exp}

Functional languages allow for easy addition of new functions on existing data 
types, but fall short in extending data types themselves (e.g. with new constructors), 
which requires modifying the source code. Object-oriented languages, on the 
other hand, make data type extension trivial through inheritance, but addition 
of new functions that work on these classes typically requires changes to class 
definition. This dilema was first discussed by Cook\cite{Cook90} and then 
accentuated by Wadler\cite{exprproblem} under the name \emph{expression problem} 
he coined. Quoting Wadler:

\emph{``The Expression Problem is a new name for an old problem. The goal is
to define a datatype by cases, where one can add new cases to the
datatype and new functions over the datatype, without recompiling
existing code, and while retaining static type safety (e.g., no
casts)''}.

Zenger and Odersky later refined the problem in the context of independently 
extensible solutions\cite{fool12} as a challenge to find an implementation 
technique which satisfies the following requirements:

\begin{itemize}
\item Extensibility in both dimensions: It should be possible to add new data 
      variants, while adapting the existing operations accordingly. It should 
      also be possible to introduce new functions.
\item Strong static type safety: It should be impossible to apply a function to 
      a data variant, which it cannot handle.
\item No modification or duplication: Existing code should neither be modified 
      nor duplicated.
\item Separate compilation: Neither datatype extensions nor addition of new 
      functions should require re-typechecking the original datatype or 
      existing functions. No safety checks should be deferred until link or 
      runtime.
\item Independent extensibility: It should be possible to combine independently 
      developed extensions so that they can be used jointly.
\end{itemize}

%Paraphrasing, the expression problem can be summarized as a problem of 
%supporting modular extensibility of both data and functions at the same time in 
%one programming language.

\noindent
Object-oriented languages further complicate the matter with the fact that 
data variants may form subtyping relationship between themselves, which brings 
in an additonal requirement:

\begin{itemize}
\item Substitutability: Operations expressed on more general data variants 
      should be applicable to more specific ones that are in subtyping relation 
      with them.
\end{itemize}

%Depending on the semantics of the language's subtyping relation, 
%substitutability requirement may turn pattern matching into an expensive 
%operation. OCaml, for example, that uses structural subtyping on its object 
%types, does not offer pattern 

\noindent
Numerous solutions have been proposed to dealing with expression problem in both 
functional and object-oriented camps, but notably very few satisfy all of the 
above requirements. We refer the reader to Zenger and Odersky's original 
manuscript for discussion of the approaches\cite{fool12}. Interestingly, most of 
the discussed object-oriented solutions were focusing on the visitor design 
pattern, which even today seems to be the most commonly used approach to dealing 
with the expression problem in practice.

\subsection{Visitor Design Pattern}
\label{sec:vdp}

%Discuss visitor design pattern and its problems.
%\begin{itemize}
%\item Intrusive - requires changes to the hierarchy
%\item Not open  - addition of new classes changes visitor interface
%\item Does not provide by default relation between visitors of base and derived classes
%\item Control inversion
%\item Cannot be generically extended to handling n arguments
%\end{itemize}

\emph{Visitor Design Pattern}\cite{DesignPatterns1993} was devised to solve a problem 
of extending existing classes with new functions in object-oriented languages. 
Consider the above Expr example and imagine we would like to provide a pretty 
printing of expressions. A typical object-oriented approach would be to 
introduce a virtual function \code{virtual void print() const = 0;} inside the 
abstract base class \code{Expr}, which will be implemented correspondingly in all derived 
classes. This works well as long as we know all the required operations on the 
abstract class in advance. Unfortunately, this is very difficult to achieve in 
reality as the code evolves, especially in production environment. To put this 
in context, imagine that after the above interface with pretty printing 
functionality has been deployed, we decided that we need a similar functionality 
that saves the expression in XML format. Adding new virtual function implies 
modifying the base class and creating a versioning problem with the code that 
has been deployed already using the old interface.

To alleviate this problem, the Visitor Design Pattern separates the 
\emph{commonality} of all such future member-functions from their 
\emph{specifics}. The former deals with identifying the most specific derived 
class of the receiver object, known to the system at the time the base class was 
designed. The latter provides implementation of the required functionality once 
the most specific derived class has been identified. The interaction between the 
two is encoded in the protocol that fixes a \emph{visitation interface} 
enumerating all known derived classes on one side and a dispatching mechanism 
that guarantees to select the most specific case with respect to the dynamic 
type of the receiver in the visitation interface. An implementation of this 
protocol for our Expr example might look as following:

\begin{lstlisting}
// Forward declaration of known derived classes
struct Value; struct Plus; ... struct Divide;
// Visitation interface
struct ExprVisitor
{
    virtual void visit(const Value&)  = 0;
    virtual void visit(const Plus&)   = 0;
    ...  // One virtual function per each known derived class
    virtual void visit(const Divide&) = 0;
};
// Abstract base and known derived classes
struct Expr { 
    virtual void accept(ExprVisitor&) const = 0; };
struct Value : Expr { ...
    void accept(ExprVisitor& v) const { v.visit(*this); } };
struct Plus  : Expr { ...
    void accept(ExprVisitor& v) const { v.visit(*this); } };
\end{lstlisting}

Note that even though implementations of \code{accept} member-functions are 
syntactically identical, a different \code{visit} is called. We rely here on the 
overload resolution mechanism of C++ to pick the most specialized \code{visit} 
member-function applicable to the static type of \code{*this}. 

%This mere code 
%maintenance convenience unfortunately, often confuses novices on what 
%is going on. We thus would like to point out that member-functions in the 
%visitation interface are not required to be called with the same name, -- we 
%could have equally well called them \code{visit_value}, \code{visit_plus} etc. 
%making the corresponding changes to calls inside \code{Value::accept}, 
%\code{Plus::accept} etc.

A user can now implement new functions by overriding \code{ExprVisitor}'s 
functions. For example:

\begin{lstlisting}
std::string to_str(const Expr* e); // Forward declaration

struct ToStrVisitor : ExprVisitor  // Converts expressions to string
{
    void visit(const Value& e) { result = std::to_string(e.value); }
    ...
    void visit(const Divide& e) { 
        result = to_str(e.exp1) + '/' + to_str(e.exp2); 
    }
    std::string result;
};
// Actual implementation based on visitor
std::string to_str(const Expr* e)
{
    ToStrVisitor v;
    e->accept(v);
    return v.result;
}
\end{lstlisting}

Function \code{eval} we presented above as well as any new function that we 
would like to add to \code{Expr} can now be implemented in much the same way, 
without the need to change base interface. This flexibility does not come for 
free though and we would like to point out some pros and cons of this solution.

The most important advantage of the visitor design pattern is possibility to add 
new operations to the class hierarchy without the necessity to change the 
interface each time. Its second most quoted advantage is typically speed -- the 
overhead of two virtual function calls incurred by the double dispatch present 
in the visitor design pattern is often negligible on the modern architectures. 
There are quite a few disadvantages however.

The solution is {\bf intrusive} since we had to inject syntactically the same 
definition of \code{accept} method into every class participating in visitation. 
It is also {\bf specific to hierarchy}, as we had to declare a visitation 
interface specific to the base class. The {\bf increased amount of boilerplate 
code} that has to be added to support the above solution also cannot go unnoticed. 
Several entities had to be forward declared because of the mutual recursivity of 
their definitions. The amount of necessary support increases, as additional 
arguments have to be passed into the visitor to be available during the 
visitation. This aspect can be seen in the example from \textsection\ref{sec:xmpl} 
where we have to store both functors inside the visitor.

More importantly, visitors {\bf hinder extensibility} of the class hierarchy: 
new classes added to the hierarchy after the visitation interface has been 
fixed, will be treated as their most derived base class present in the interface.
A solution to this problem has been proposed in the form of \emph{Extensible 
Visitors with Default Cases}\cite[\textsection 4.2]{Zenger:2001}, however the 
solution, after remapping it onto C++, has problems of its own, discussed in 
details in related work \textsection\ref{sec:rw}.

%The visitation interface 
%hierarchy can easily be grown linearly (adding new cases for the new classes in 
%the original hierarchy each time), but independent extensions by different  
%authorities require developer's intervention to unify them all, before they can 
%be used together. This may not be feasible in environments that use dynamic 
%linking. To avoid writing even more boilerplate code in new visitors, the 
%solution would require usage of virtual inheritance, which typically has 
%an overhead of extra memory dereferencing. On top of the double dispatch already 
%present in the visitor pattern, the solution will incur two additional virtual 
%calls and a dynamic cast for each level of visitor extension. Additional double 
%dispatch is incurred by forwarding of default handling from base visitor to a 
%derived one, while the dynamic cast is required for safety and can be replaced 
%with a static case when visitation interface is guaranteed to be grown linearly 
%(extended by one authority only). Yet another virtual call is required to be 
%able to forward computations to subcomponents on tree-like structures to the 
%most derived visitor. This last function lets one avoid the necessity of using 
%heap to allocate a temporary visitor through the \emph{Factory Design 
%Pattern}\cite{DesignPatterns1993} used in \emph{Extensible Visitor} solution 
%originally proposed by Krishnamurti, Felleisen and Friedman\cite{Krishnamurthi98}.

Once all the boilerplate related to visitors has been written and the visitation 
interface has been fixed we are still left with some annoyances incurred by the 
pattern. One of them is the necessity to work with the {\bf control inversion} 
that visitors put in place. Because of it we have to save any local state and 
any arguments that some of the \code{visit} callbacks might need from the 
calling environment. Similarly, we have to save the result of the visitation, 
as we cannot assume that all the visitors that will potentially be implemented 
on a given hierarchy will use the same result type. Using visitors in a generic 
algorithm requires even more precautions. We summarize these visitor-related 
issues in the following motivating example, followed by an illustration of a 
pattern-matching solution to the same problem enabled with our library.

\subsection{Motivating Example}
\label{sec:xmpl}

While comparing generic programming facilities available to functional and 
imperative languages (mainly Haskell and C++), Dos Reis and J\"arvi present the 
following example in Haskell describing a sum functor\cite{DRJ05}:

\begin{lstlisting}[language=Haskell]
data Either a b = Left a | Right b

eitherLift :: (a -> c) -> (b -> d) -> Either a b -> Either c d
eitherLift f g (Left  x) = Left  (f x)
eitherLift f g (Right y) = Right (g y)
\end{lstlisting}

In simple words, the function \codehaskell{eitherLift} above takes two functions and an 
object and depending on the actual type constructor the object was created with, 
calls first or second function on the embedded value, encoding the result 
correspondingly.

Its equivalent in C++ is not straightforward. The idiomatic handling of 
discriminated unions in C++ typically assumes use of the \emph{Visitor Design 
Pattern}\cite{DesignPatterns1993}.

\begin{lstlisting}
template <class X, class Y> class Either;
template <class X, class Y> class Left;
template <class X, class Y> class Right;

template <class X, class Y>
struct EitherVisitor {
    virtual void visit(const  Left<X,Y>&) = 0;
    virtual void visit(const Right<X,Y>&) = 0;
};

template <class X, class Y>
struct Either {
    virtual @$\sim$@Either() {}
    virtual void accept(EitherVisitor<X,Y>& v) const = 0;
};

template <class X, class Y>
struct Left : Either<X,Y> {
    const X& x;
    Left(const X& x) : x(x) {}
    void accept(EitherVisitor<X,Y>& v) const { v.visit(*this); }
};

template <class X, class Y>
struct Right : Either<X,Y> {
    const Y& y;
    Right(const Y& y) : y(y) {}
    void accept(EitherVisitor<X,Y>& v) const { v.visit(*this); }
};
\end{lstlisting}

The code above defines the necessary parameterized data structures as well as a 
correspondingly parameterized visitor class capable of introspecting it at 
run-time. The authors agree with us \emph{``The code has a fair amount of 
boilerplate to simulate pattern matching...''}\cite{DRJ05} The actual 
implementation of \codehaskell{lift} in C++ now amounts to declaring and 
invoking a visitor:

\begin{lstlisting}
template <class X, class Y, class S, class T>
const Either<S,T>& lift(const Either<X,Y>& e, S f(X), T g(Y))
{
    typedef S (*F)(X);
    typedef T (*G)(Y);
    struct Impl : EitherVisitor<X,Y> {
        F f;
        G g;
        const Either<S,T>* value;
        Impl(F f, G g) : f(f), g(g), value() {}
        void visit(const Left<X,Y>& e) {
            value = left<S,T>(f(e.x));
        }
        void visit(const Right<X,Y>& e) {
            value = right<S,T>(g(e.y));
        }
    };
    Impl vis(f, g);
    e.accept(vis);
    return *vis.value;
}
\end{lstlisting}

The same function expressed with our pattern-matching facility seems to be much 
closer to the original Haskell definition:

\begin{lstlisting}[keepspaces,columns=flexible]
template <class X, class Y, class S, class T>
const Either<S,T>* lift(const Either<X,Y>& e, S f(X), T g(Y))
{
    Match(e)
      Case(( Left<X,Y>), x) return  left<S,T>(f(x));
      Case((Right<X,Y>), y) return right<S,T>(g(y));
    EndMatch
}
\end{lstlisting}

This is also as fast as the visitor solution, but unlike the visitors based 
approach it neither requires \code{EitherVisitor}, nor any of the injected 
\code{accept} member-functions. We do require binding definitions though to be 
able to bind variables \code{x} and \code{y}:

%@\footnote{We need to take the first argument in parentheses to avoid interpretation of comma in template argument list by the preprocessor}@
%\footnote{Definitions of obvious functions \code{left} and \code{right} have 
%been ommitted in both cases.}

\begin{lstlisting}[keepspaces,columns=flexible]
template <class X, class Y> 
    struct bindings<Left<X,Y>>  { CM(0, Left<X,Y>::x); };
template <class X, class Y> 
    struct bindings<Right<X,Y>> { CM(0,Right<X,Y>::y); };
\end{lstlisting}

Note that these binding definitions are made once for all possible instantiations 
with the use of partial template specialization in C++ and would not be needed 
if we implemented pattern matching in a compiler rather than a library.

\subsection{Summary}

We present a functional style pattern matching for C++ built as a library. Our solution:

  \begin{itemize}
  \item Is open, non-intrusive and avoids the control inversion typical for visitors.
  \item Can be applied retroactively to any polymorphic or tagged class hierarchy.
  \item Provides a unified syntax for various encodings of extensible 
        hierarchycal datatypes in C++.
  \item Generalizes n+k patterns, leaving the controversial semantic choices to the user.
  \item Supports a limited form of views.
  \item We provide performance and ease of use comparison based on real code.
  \end{itemize}

\noindent
Our technique can be used in a compiler and/or library setting to implement 
facilities that depend on dynamic type or run-time properties of objects: e.g. 
type switching, type testing, pattern matching, predicate dispatch, 
multi-methods etc. We also look at different approaches to endoding algebraic 
data types in C++ and present a unified pattern-matching syntax that works 
uniformly with all of them. 
We generalize Haskell's n+k patterns\cite{haskell98} to any invertible operations. 
Semantics issues that typically accompany n+k pattern are handled transparently 
by forwarding the problem into the concepts domain, thanks to the fact that we 
work in a library setting. We also provide support for views in a form that 
resembles extractors in Scala. A practical benefit of our solution is that it 
can be used right away with any compiler with a descent support of C++0x without
requiring to install any additional tools or preprocessors.

The rest of this paper is structured as following. In Section~\ref{sec:bg}, we 
present evolution of pattern matching in different languages, presenting 
informally through example commonly used terminology and semantics of various 
pattern-matching constructs. Section~\ref{sec:pm} presents various approaches 
that are taken in C++ to implementing algebraic data types as well as 
demonstrates uniform handling of them in our pattern-matching library. 
Sections~\ref{sec:syn} and~\ref{sec:sem} describe the syntax and semantics of 
our pattern matching facilities. Section~\ref{sec:impl} discusses our technique 
that makes type switching efficient, while section~\ref{sec:eval} provides its 
performance evaluation against some common alternatives. Section~\ref{sec:rw} 
discusses related work, and section~\ref{sec:cc} concludes by discussing some 
future directions and possible improvements.

\section{Background} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:bg}

Pattern matching in the context of a programming language was first introduced 
in a string manipulation language SNOBOL\cite{SNOBOL64}. Its fourth 
reincarnation SNOBOL4 had patterns as first-class data types providing 
operations of concatenation and alternation on them\cite{SNOBOL71}. The first 
reference to a pattern-matching construct that resembles the one found in 
statically typed functional languages today is usually attributed to Burstall 
and his work on structural induction\cite{Burstall69provingproperties}.

In the context of object-oriented programming, pattern matching has been first 
explored in Pizza programming language\cite{Odersky97pizzainto}. These efforts 
have been continued in Scala\cite{Scala2nd} and together with notable work of 
Burak Emir on \emph{Object-Oriented Pattern Matching}\cite{EmirThesis} have 
resulted in incorporation of pattern matching into the language.

%The first tree based pattern matching methods were found in Fred McBride's 
%extension of LISP in 1970.

%ML and Haskell further popularized pattern matching ...

Pattern matching has been closely related to \emph{algebraic data types} and 
\emph{equational reasoning} since the early days of functional programming.
In languages like ML and Haskel an \emph{Algebraic Data Type} is a data type 
each of whose values is picked from a disjoint sum of (possibly recursive) data 
types, called \emph{variants}. Each of the variants is marked with a unique 
symbolic constant called \emph{constructor}, while the set of all constructors 
of a given type is called \emph{signature}. Constructors provide a convenient 
way of creating a value of its variant type as well as a way of discriminating 
its variant type from the algebraic data type through pattern matching.

Algebraic data type \codeocaml{expr} from Section~\ref{sec:intro} consists of 5 
variants, marked with constructors \codeocaml{Value}, \codeocaml{Plus}, 
\codeocaml{Minus}, \codeocaml{Times} and \codeocaml{Divide} respectively. 
Constructor \codeocaml{Value} expects a value of type \codeocaml{int} during 
construction, as well as any pattern that admits values of type \codeocaml{int} 
during decomposition through pattern matching. Similarly, the other four 
constructors expect a value of a cartesian product of two \codeocaml{expr} 
types during construction, as well as any pattern that would admit a value of 
such type during decomposition.

Algebraic data types can be parameterized and recursive, as demonstrated by the 
following Haskell code that defines a binary tree parameterized on type 
\codehaskell{k} of keys and type \codehaskell{d} of data stored in the nodes:

\begin{lstlisting}[language=Haskell]
data Tree k d = Node k d (Tree k d) (Tree k d) | Leaf
\end{lstlisting}

Naturally, they can be decomposed in a generic algorithm like the function 
\code{find} below, defined through case analysis on the tree's structure:

\begin{lstlisting}[language=Haskell]
find :: (Ord k) => k -> Tree k d -> Maybe d
find i Leaf = Nothing
find i (Node key item left right) = 
    if i == key 
    then Just item 
    else 
        if i [<] key 
        then find i left 
        else find i right
\end{lstlisting}

The set of values described by a given algebraic data type is defined 
inductively as the least set closed under constructor functions of its variants.
Algebraic data types draw their name from the practice of using case distinction 
in mathematical function definitions and proofs that involve \emph{algebraic 
terms}.

One of the main differences of algebraic data types from classes in 
object-oriented languages is that an algebraic data type definition is 
\emph{closed} because it fixes the structure of its instances once and for all. 
Once we have listed all the variants a given algebraic data type may have we 
cannot extend it with new variants without modifying its definition. This is not 
the case in object-oriented languages, where classes are \emph{open} to 
extension through subclassing. Notable exceptions to this restriction in 
functional community are \emph{polymorphic variants} in OCaml\cite{garrigue-98} 
and \emph{open data types} in Haskell\cite{LohHinze2006}, which allow addition 
of new variants later. These extensions, however, are simpler than object-oriented 
extensions as neither polymorphic variants nor open data types form subtyping 
relation between themselves: open data types do not introduce any subtyping 
relation, while the subtyping relation on polymorphic variants is a 
\emph{semantic subtyping} similar to that of XDuce\cite{HosoyaPierce2000}, which 
is based on the subset relation between values of the type. In either case they 
maintain the important property that each value of the underlain algebraic data 
type belongs to exactly one disjoint subset tagged with a constructor. The 
\emph{nominative subtyping} of object-oriented languages does not usually have 
this disjointness making classes effectively have multiple types. In particular, 
the case of disjoint constructors can be seen as a degenerated case of a flat 
class hierarchy among the multitude of possible class hierarchies.

Closeness of algebraic data types is particularly useful in reasoning about 
programs by case analysis and allows the compiler to perform an automatic 
\emph{incompleteness} check -- test of whether a given match expression covers all 
possible cases. A related notion of \emph{redundancy} checking arises from the 
tradition of using \emph{first-fit} strategy in pattern matching. It warns the 
user of any \emph{case clause} inside a \emph{matching expression} that will 
never be entered because of preceding one being more general. Object-oriented 
languages, especially C++, typically prefer \emph{best-fit} strategy (e.g. for 
overload resolution and class template specialization) because it is not prone 
to errors where semantics of a statement might change depending on the ordering 
of preceding definitions. The notable exception in C++ semantics that prefers 
the \emph{first-fit} strategy is ordering of \code{catch} handlers of a 
try-block. Similarly to functional languages the C++ compiler will perform 
\emph{redundancy} checking on catch handlers and issue a warning that lists the 
redundant cases. We use this property of C++ type system to perform redundancy 
checking of our match statements in \textsection\ref{sec:redun}.

The patterns that work with algebraic data types we have seen so far are 
generally called \emph{tree patterns} or \emph{data constructor patterns}. 
Special cases of these patterns are \emph{list patterns} and \emph{tuple 
patterns}. The former lets one split a list into a sequence of elements in its 
beginning and a tail with the help of list constructor \codehaskell{:} and an 
empty list constructor \codehaskell{[]} e.g. \codehaskell{[x:y:rest]}. The 
latter does the same with tuples using tuple constructor 
\codehaskell{(,,...,)} e.g. \codehaskell{([x:xs],'b',(1,2.0),"hi",True)}.

Pattern matching is not used solely with algebraic data types and can equally 
well be applied to built-in types. The following Haskell code defines factorial 
function in the form of equations:

\begin{lstlisting}[language=Haskell]
factorial 0 = 1
factorial n = n * factorial (n-1)
\end{lstlisting}

Here 0 in the left hand side of the first \emph{equation} is an example of a 
\emph{value pattern} (also known as \emph{constant pattern}) that will only 
match when the actual argument passed to the function factorial is 0. The 
\emph{variable pattern} \codehaskell{n} (also referred to as \emph{identifier 
pattern}) in the left hand side of the second equation will match any value, 
\emph{binding} variable \codehaskell{n} to that value in the right hand side of 
equation. Similarly to variable  
pattern, \emph{wildcard pattern} \codehaskell{_} will match any value with the 
exception that the matched value will not be bound to any variable. Value 
patterns, variable patterns and wildcard patterns are generally called 
\emph{primitive patterns}. Patterns like variable and wildcard patterns that 
never fail to match are called \emph{irrefutable}, in contrast to 
\emph{refutable} patterns like value patterns, which may fail to match.

In Haskell 98\cite{Haskell98Book} the above definition of factorial could also 
be written as:

\begin{lstlisting}[language=Haskell]
factorial 0 = 1
factorial (n+1) = (n+1) * factorial n
\end{lstlisting}

The \codehaskell{(n+1)} pattern in the left hand side of equation is an example of 
\emph{n+k pattern}. Accordingly to its informal semantics ``Matching an $n+k$ 
pattern (where $n$ is a variable and $k$ is a positive integer literal) against 
a value $v$ succeeds if $v \ge k$, resulting in the binding of $n$ to $v-k$, and 
fails otherwise''\cite{haskell98}. n+k patterns were introduced into Haskel to 
let users express inductive functions on natural numbers in much the same way as 
functions defined through case analysis on algebraic data types. Besides 
succinct notation, such language feature could facilitate automatic proof of 
termination of such functions by compiler. Peano numbers, used as an analogy to 
algebraic data type representation of natural numbers, is not always the best 
abstraction for representing other mathematical operations however. This,  
together with numerous ways of defining semantics of generalized n+k patterns 
were some of the reasons why the feature was never generalized in Haskell to 
other kinds of expressions, even though there were plenty of known applications. 
Moreover, numerous debates over semantics and usefulness of the feature 
resulted in n+k patterns being removed from the language altogether in Haskell 
2010 standard\cite{haskell2010}. Generalization of n+k patterns, called 
\emph{application patterns} has been studied by Nikolaas N. Oosterhof in his 
Master's thesis\cite{OosterhofThesis}.

While n+k patterns were something very few languages had, another common feature of 
many programming languages with pattern matching are guards. A \emph{guard} 
is a predicate attached to a pattern that may make use of the variables bound in 
it. The result of its evaluation will determine whether the case clause and the 
body associated with it will be \emph{accepted} or \emph{rejected}. The 
following OCaml code for $exp$ language from Section~\ref{sec:intro} defines the 
rules for factorizing expressions $e_1e_2+e_1e_3$ into $e_1(e_2+e_3)$ and 
$e_1e_2+e_3e_2$ into $(e_1+e_3)e_2$ with the help of guards spelled out after 
keyword \codeocaml{when}:

\begin{lstlisting}[language=Caml,keepspaces,columns=flexible]
let factorize e =
    match e with
      Plus(Times(e1,e2), Times(e3,e4)) when e1 = e3 
          -> Times(e1, Plus(e2,e4))
    | Plus(Times(e1,e2), Times(e3,e4)) when e2 = e4 
          -> Times(Plus(e1,e3), e4)
    |   e -> e
    ;;
\end{lstlisting}

One may wonder why we could not simply write the above case clause as 
\codeocaml{Plus(Times(e,e2), Times(e,e4))} to avoid the guard? Patterns that 
permit use of the same variable in them multiple times are called 
\emph{equivalence patterns}, while the requirement of absence of such patterns 
in a language is called \emph{linearity}. Neither OCaml nor Haskell support such 
patterns, while Miranda\cite{Miranda85} as well as Tom's pattern matching 
extension to C, Java and Eiffel\cite{Moreau:2003} support \emph{non-linear 
patterns}.

The example above illustrates yet another common pattern-matching facility -- 
\emph{nesting of patterns}. In general, a constructor pattern composed of a 
linear vector of (distinct) variables is called a \emph{simple pattern}. The 
same pattern composed not only of variables is called \emph{nested pattern}.
Using nested patterns, with a simple expression in the case clause we could
define a predicate that tests the top-level expression to be tagged with a
\codeocaml{Plus} constructor, while both of its arguments to be marked with 
\codeocaml{Times} constructor, binding their arguments (or potentially pattern 
matching further) respectively. Note that the visitor design pattern does not 
provide this level of flexibility and each of the nested tests might have 
required a new visitor to be written. Nesting of patterns like the one above is 
typically where users resort to \emph{type tests} and \emph{type casts} that in 
case of C++ can be combined into a single call to \code{dynamic_cast}.

Related to nested patterns are \emph{as-patterns} that help one take a value 
apart while still maintaining its integrity. The following rule could have been 
a part of a hypothetical rewriting system in OCaml similar to the one above. Its 
intention is to rewrite expressions of the form $\frac{e_1/e_2}{e_3/e_4}$ into 
$\frac{e_1}{e_2}\frac{e_4}{e_3} \wedge e_2\neq0 \wedge e_3\neq0 \wedge e_4\neq0$.

\begin{lstlisting}[language=Caml,keepspaces,columns=flexible]
    | Divide(Divide(_,e2) as numerator, Divide(e3,e4))
          -> Times(numerator, Divide(e4, e3))
\end{lstlisting}

We introduced a name ``numerator'' as a synonym of the result of matching the 
entire sub-expression \codeocaml{Divide(_,e2)} in order to refer it without 
recomposing in the right-hand side of the case clause. We omitted the 
conjunction of relevant non-zero checks for brevity, one can see that we will 
need access to \codeocaml{e2} in it however.

Decomposing algebraic data types through pattern matching has an important 
drawback that was originally spotted by Wadler\cite{Wadler87}: they expose 
concrete representation of an abstract data type, which conflicts with the 
principle of \emph{data abstraction}. To overcome the problem he proposed the 
notion of \emph{views} that represent conversions between different 
representations that are implicitly applied during pattern matching. As an 
example, imagine polar and cartesian representations of complex numbers. A user 
might choose polar representation as a concrete representation for the abstract 
data type \codeocaml{complex}, treating cartesian representation as view or vice 
versa:\footnote{We use syntax from Wadler's original paper for this example}

\begin{lstlisting}[language=Haskell,columns=flexible]
complex ::= Pole real real
view complex ::= Cart real real
  in  (Pole r t) = Cart (r * cos t) (r * sin t)
  out (Cart x y) = Pole (sqrt(x^2 + y^2)) (atan2 x y)
\end{lstlisting}

The operations then might be implemented in whatever representation is the most 
suitable, while the compiler will implicitly convert representation if needed:

\begin{lstlisting}[language=Haskell,columns=flexible]
  add  (Cart x1 y1) (Cart x2 y2) = Cart (x1 + x2) (y1 + y2)
  mult (Pole r1 t1) (Pole r2 t2) = Pole (r1 * r2) (t1 + t2)
\end{lstlisting}

The idea of views were later adopted in various forms in several languages: 
Haskell\cite{views96}, Standard ML\cite{views98}, Scala (in the form of 
\emph{extractors}\cite{EmirThesis}) and F$\sharp$ (under the name of 
\emph{active patterns}\cite{Syme07}).

%Views in functional programming languages [92, 71] are conversions from one data type to
%another that are implicitly applied in pattern matching. They play a role similar to extractors
%in Scala, in that they permit to abstract from the concrete data-type of the matched objects.
%However, unlike extractors, views are anonymous and are tied to a particular target data
%type.

Logic programming languages like Prolog take pattern matching to even greater 
level. The main difference between pattern matching in logic languages and 
functional languages is that functional pattern matching is a ``one-way'' 
matching where patterns are matched against values, possibly binding some 
variables in the pattern along the way. Pattern matching in logic programming is 
``two-way'' matching based on \emph{unification} where patterns can be matched 
against other patterns, possibly binding some variables in both patterns and 
potentially leaving some variables \emph{unbound} or partially bound -- i.e. 
bound to patterns. A hypothetical example of such functionality can be matching 
a pattern \codeocaml{Plus(x,Times(x,1))} against another pattern 
\codeocaml{Plus(Divide(y,2),z)}, which will result in binding \codeocaml{x} to a 
\codeocaml{Divide(y,2)} and \codeocaml{z} to \codeocaml{Times(Divide(y,2),1)} 
with \codeocaml{y} left unbound, leaving both \codeocaml{x} and \codeocaml{z} 
effectively a pattern.

\subsection{Expression Templates}

Interestingly enough C++ has a pure functional sublanguage in it that has a 
striking similarity to ML and Haskell. The sublanguage in question is template 
facilities of C++ that has been shown to be Turing 
complete\cite{veldhuizen:templates_turing_complete}. 

Haskell definition of \code{factorial} we saw earlier can be rewritten in 
template sublanguage of C++ as following:

\begin{lstlisting}
template <int N> 
    struct factorial { enum { result = N*factorial<N-1>::result }; };
template <>
    struct factorial<0> { enum { result = 1 }; };
\end{lstlisting}

\noindent
One can easily see similarity with equational definitions in Haskell, with the 
exception that more specific cases (specialization for 0) have to follow the 
general definition in C++. The main difference between Haskell definition and 
its C++ counterpart is that the former describes computations on \emph{run-time 
values}, while the latter can only work with \emph{compile-time values}.

Turns out we can even express our $exp$ language using this functional 
sublanguage:

\begin{lstlisting}
template <class T>
struct value {
    value(const T& t) : m_value(t) {}
    T m_value;
};

template <class T>
struct variable {
    variable() : m_value() {}
    T m_value;
};

template <typename E1, typename E2>
struct plus {
    plus(const E1& e1, const E2& e2) : m_e1(e1), m_e2(e2) {}
    const E1 m_e1; const E2 m_e2;
};

// ... definitions of other expressions
\end{lstlisting}

\noindent The idea is that expressions can be composed out of subexpressions, 
whose shape (type) is passed as arguments to above templates. Explicit 
description of such expressions is very tedious however and is thus never 
expressed directly, but as a result of corresponding operations: 

\begin{lstlisting}[keepspaces,columns=flexible]
template <typename T>
    value<T> val(const T& t) { return value<T>(t); }
template <typename E1, typename E2>
    plus<E1,E2> operator+(const E1& e1, const E2& e2)
    { return plus<E1,E2>(e1,e2); }
\end{lstlisting}

\noindent With this, one can now capture various expressions as following:

\begin{lstlisting}
variable<int> v;
auto x = v + val(3);
\end{lstlisting}

\noindent The type of variable \code{x} -- \code{plus<variable<int>,value<int>>}
 -- captures the structure of the expression, while the values inside of it 
represent various subexpressions the expression was created with. Such an 
expression can be arbitrarily, but finitely nested. Note that value 3 is not 
added to the value of variable \code{v} here, but the expression \code{v+3} is 
recorded, while the meaning to such expression can be given differently in 
different contexts. A general observation is that only the shape of the 
expression becomes fixed at compile time, while the values of variables involved 
in it can be changed arbitrarily at run time, allowing for \emph{lazy 
evaluation} of the expression. Polymorphic function \code{eval} below implements 
just that:

\begin{lstlisting}[keepspaces,columns=flexible]
template <typename T> 
    T eval(const value<T>& e) { return e.m_value; }
template <typename T> 
    T eval(const variable<T>& e) { return e.m_value; }
template <typename E1, typename E2> 
    auto eval(const plus<E1,E2>& e) 
         -> decltype(eval(e.m_e1) + eval(e.m_e2))
            { return eval(e.m_e1) + eval(e.m_e2); }
\end{lstlisting}

\noindent One can now modify value of the variable \code{v} and re-evaluate 
expression as following:

\begin{lstlisting}
v = 7;           // assumes overloading of assignment
int r = eval(x); // returns 10
\end{lstlisting}

\noindent The above technique for lazy evaluation of expressions was 
independently invented by Todd Veldhuizen and David Vandevoorde and is generally 
known in the C++ community by the name \emph{Expression Templates} that Todd 
coined\cite{Veldhuizen95expressiontemplates, vandevoorde2003c++}.  

Note again how implementation of \code{eval} resembles equations in Haskell that 
decompose an algebraic data type. The similarities are so striking that there 
were attempts to use Haskell as a pseudo code language for template 
metaprogramming in C++\cite{Milewski11}. A key observation in this analogy is 
that partial and explicit template specialization of C++ class templates are 
similar to defining equations for Haskell functions. Variables introduced via 
template clause of each equation serve as \emph{variable patterns}, while the 
names of actual templates describing arguments serve as \emph{variant 
constructors}. An important difference between the two is that Haskell's 
equations use \emph{first-fit} strategy making order of equations important, 
while C++ uses \emph{best-fit} strategy, thus making the order irrelevant.

Patterns expressed this way can be arbitrarily nested as long as they can be 
expressed in terms of the types involved and not the values they store. Using 
the above example, for instance, it is very easy to specialize \code{eval} for 
an expression of form $c_1*x+c_2$ where $c_i$ are some (not known) constant 
values and $x$ is any variable. Specializing for a concrete instance of that 
expression $2*x+3$ will be much harder, because in the representation we chose 
values 2 and 3 become run-time values and thus cannot participate in 
compile-time computations anymore. In this case we could have devised a template 
that allocates a dedicated type for each constant making such value part of the 
type:

\begin{lstlisting}[keepspaces,columns=flexible]
template <class T, T t> struct constant {};

template <typename T, T t>
    T eval(const constant<T,t>& e) { return t; }
template <typename E>
    auto eval(const times<constant<int,0>,E>& e) 
        -> decltype(eval(e.m_e2)) 
            { return (decltype(eval(e.m_e2)))(0); }
template <typename E>
    auto eval(const times<E,constant<int,0>>& e) 
        -> decltype(eval(e.m_e1)) 
            { return (decltype(eval(e.m_e1)))(0); }
\end{lstlisting}

\noindent Here the first equation for \code{eval} describes the necessary general 
case for handling expressions of type \code{constant<T,t>}, while the other two 
are redundant cases that can be seen as an optimization detecting expressions of 
the form $e*0$ and $0*e$ for any arbitrary expression $e$ and returning 0 
without actually computing $e$.

Unfortunately, a similar pattern to detect expressions of the form $x-x$ for any 
variable $x$ cannot be expressed because expression templates are blind to 
object identity and can only see their types. This means that expression 
templates of the form $x-y$ are indisthinguishable at compile time from 
expressions of the form $x-x$ because their types are identical.

Nevertheless, with all the limitations, expression templates provide an 
extremely powerful abstraction mechanism, which we use to express a 
pattern-language for our SELL. Coincidentally, we employ the compile-time 
pattern-matching facility already supported by C++ as a meta-language to 
implement its run-time counterpart.

\section{Pattern Matching for C++} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:pm}

%In order to be able to provide a common syntax for these representations, we 
%need to understand better similarities and differences between them. Before we 
%look into them let's fix some terminology.

When we deal with pattern matching, the static type of the original expression 
we are matching may not necessarily be the same as the type of expression we 
match it with. We call the original expression a \emph{selector} and its static 
type -- \emph{selector type}. We call the type we are trying to match selector 
against -- a \emph{target type}.

In the simplest case, detecting that the target type is a given type or a type 
derived from it, is everything we want to know. We refer to such a use-case as 
\emph{type testing}. In the next simplest case, besides testing we might want to 
get a pointer or a reference to the target type of selector as casting it to such 
a type may involve a non-trivial computation only a compiler can safely 
generate. We refer to such a use-case as \emph{type identification}. Type 
identification of a given selector against multiple target types is typically 
referred to as \emph{type switching}.

Once we uncovered the target type, we may want to be able to decompose it 
\emph{structurally} (when the target type is a \emph{structured} data type like 
array, tuple or class) or \emph{algebraically} (when the target type is a scalar 
data type like \code{int} or \code{double}). Structural decomposition in our 
library can be performed with the help of \emph{tree patterns}, while algebraic 
decomposition can be done with the help of \emph{generalized n+k patterns}.

\subsection{Algebraic Data Types in C++}
\label{sec:adt}

C++ does not have a direct support of algebraic data types, but they can usually 
be emulated in a number of ways. A pattern-matching solution that strives to be 
general will have to account for different encodings and be applicable to all of 
them.

Consider an ML data type of the form:

\begin{lstlisting}[language=ML,keepspaces,columns=flexible,escapechar=@]
datatype DT = @$C_1$@ of {@$L_{11}:T_{11},...,L_{1m}:T_{1m}$@} 
              | ...
              | @$C_k$@ of {@$L_{k1}:T_{k1},...,L_{kn}:T_{kn}$@}
\end{lstlisting}

\noindent There are at least 3 different ways to encode them in C++. Following 
Emir, we will refer to them as \emph{encodings}:

\begin{itemize}
\item Polymorphic Base Class
\item Tagged Class
\item Discriminated Union
\end{itemize}

The first two encodings are inherently \emph{open} because the classes can be 
arbitrarily extended through subclassing. The last encoding is inherently 
\emph{closed} because we cannot add more members to the union without modifying 
its definition. For brevity, we will refer to these encoding throughout the rest 
of the paper as \emph{polymorphic}, \emph{tagged} and \emph{union} encodings 
respectively.

\subsubsection{Polymorphic Base Class}
\label{sec:pbc}

In this encoding user declares a polymorphic base class \code{DT} that will 
be extended by classes representing all the variants. Base class might declare 
several virtual functions that will be overridden by derived classes, for example 
\code{accept} used in a Visitor Design Pattern.

\begin{lstlisting}[keepspaces,columns=flexible]
class DT { virtual @$\sim$@DT{} };
class @$C_1$@ : public DT {@$T_{11} L_{11}; ... T_{1m} L_{1m};$@} 
...
class @$C_k$@ : public DT {@$T_{k1} L_{k1}; ... T_{kn} L_{kn};$@} 
\end{lstlisting}

The uncover the actual variant of such an algebraic data type, the user might 
use \code{dynamic_cast} to query one of the $k$ expected run-time types (an 
approach used by Rose\cite{SQ03}) or she might employ a visitor design pattern 
devised for this algebraic data type (an approach used by Pivot\cite{Pivot09} 
and Phoenix\cite{Phoenix}). The most attractive feature of this approach is that 
it is truly open as we can extend classes arbitrarily at will (leaving the 
orthogonal issues of visitors aside).

\subsubsection{Tagged Class}
\label{sec:tc}

This encoding is similar to the \emph{Polymorphic Base Class} in that we use 
derived classes to encode the variants. The main difference is that the user 
designates a member in the base class, whose value will uniquely 
determine the most derived class a given object is an instance of. Constructors 
of each variant $C_i$ are responsible for properly initializing the dedicated 
member with a unique value $c_i$ associated with that variant. Clang\cite{Clang} 
among others uses this approach.

\begin{lstlisting}[keepspaces,columns=flexible]
class DT { enum kinds {@$c_1, ..., c_k$@} m_kind; };
class @$C_1$@ : public DT {@$T_{11} L_{11}; ... T_{1m} L_{1m};$@} 
...
class @$C_k$@ : public DT {@$T_{k1} L_{k1}; ... T_{kn} L_{kn};$@} 
\end{lstlisting}

In such scenario the user might use a simple switch statement to uncover the 
type of the variant combined with a \code{static_cast} to properly cast the 
pointer or reference to an object. People might prefer this encoding to the one 
above for performance reasons as it is possible to avoid virtual dispatch with 
it altogether. Note, however, that once we allow for extensions and not limit 
ourselves with encoding algebraic data types only it also has a significant 
drawback in comparison to the previous approach: we can easily check that given 
object belongs to the most derived class, but we cannot say much about whether 
it belongs to one of its base classes. A visitor design pattern can be 
implemented to take care of this problem, but control inversion that comes along 
with it will certainly diminish the convenience of having just a switch 
statement. Besides, forwarding overhead might lose some of the performance 
benefits gained originally by putting a dedicated member into the base class.

\subsubsection{Discriminated Union}
\label{sec:du}

This encoding is popular in projects that are either implemented in C or 
originated from C before coming to C++. It involves a type that contains a union 
of its possible variants, discriminated with a dedicated value stored as a part 
of the structure. The approach is used by EDG front-end\cite{EDG} and many others.

\begin{lstlisting}[keepspaces,columns=flexible]
struct DT
{
    enum kinds {@$c_1, ..., c_k$@} m_kind;
    union {
        struct @$C_1$@ {@$T_{11} L_{11}; ... T_{1m} L_{1m};$@} @$C_1$@;
        ...
        struct @$C_k$@ {@$T_{k1} L_{k1}; ... T_{kn} L_{kn};$@} @$C_k$@; 
    };
};
\end{lstlisting}

As before, the user can use a switch statement to identify the variant $c_i$ and 
then access its members via $C_i$ union member. This approach is truly closed, as 
we cannot add new variants to the underlain union without modifying class 
definition. 

Note also that in this case both selector type and target types are the same and 
we use an integral constant to distinguish which member(s) of the underlain union 
is active now. In the other two cases the type of a selector is a base class of 
the target type and we use either run-time type information or the integral 
constant associated by the user with the target type to uncover the target type. 

\subsection{Pattern Matching Syntax}
\label{sec:syn}

We present rather informally abstract syntax enabled by our SELL in order to 
improve clarity of the presentation. We do not try to capture all of the C++ 
syntax here because we do not in fact change or extend the language. All the 
facilities available through our library are nothing else but a syntactic sugar 
enabled through the ``clever'' use of template and macro mechanisms already 
present in the language. We do make use of several non-terminals from the C++ 
grammar to put the use of our constructs into context. For the complete C++ 
grammar we refer the curious reader to Appendix A of the current C++ 
standard\cite{C++0x}.

% TODO:
%()     Function call
%[]     Array subscripting
%*      Indirection (dereference)
%&      Address-of
%sizeof Size-of

\begin{center}
\begin{tabular}{rp{0em}cl}
\Rule{match statement}     & $M$       & \is{}  & \code{Match(}$e$\code{)} $\left[C s^*\right]^*$ \code{EndMatch} \\
\Rule{case clause}         & $C$       & \is{}  & \code{Case(}$T\left[,x\right]^*$\code{)} \\
                           &           & \Alt{} & \code{Qua(} $T\left[,\omega\right]^*$\code{)} \\
                           &           & \Alt{} & \code{Otherwise(}$\left[,x\right]^*$\code{)} \\
\Rule{target expression}   & $T$       & \is{}  & $\tau$ \Alt{} $l$ \Alt{} $\nu$ \\
\Rule{view}                & $\nu$     & \is{}  & \code{view<}$\tau,l$\code{>} \\
\Rule{match expression}    & $m$       & \is{}  & $\pi(e)$ \\
\Rule{pattern}             & $\pi$     & \is{}  & $\_$ \Alt{} $\eta$ \Alt{} $\varrho$ \Alt{} $\mu$ \Alt{} $\varsigma$ \Alt{} $\chi$ \\
\Rule{extended pattern}    & $\omega$  & \is{}  & $\pi$ \Alt{} $c$ \Alt{} $x$ \\
\Rule{tree pattern}        & $\mu$     & \is{}  & \code{match<}$\nu|\tau\left[,l\right]$\code{>(}$\omega^*$\code{)} \\
\Rule{guard pattern}       & $\varrho$ & \is{}  & $\pi \models \xi$ \\
\Rule{n+k pattern}         & $\eta$    & \is{}  & $\chi$ \Alt{} $\eta \oplus c$ \Alt{} $c \oplus \eta$ \Alt{} $\ominus \eta$ \Alt{} $(\eta)$ \Alt{} $\_$ \\
\Rule{wildcard pattern}    & $\_^{wildcard}$ \\
\Rule{variable pattern}    & $\chi$    & \is{}  & $\kappa$ \Alt{} $\iota$ \\
\Rule{value pattern}       & $\varsigma^{value\langle\tau\rangle}$ \\
\Rule{xt variable}         & $\kappa^{variable\langle\tau\rangle}$ \\
\Rule{xt reference}        & $\iota^{var\_ref\langle\tau\rangle}$  \\
\Rule{xt expression}       & $\xi$     & \is{}  & $\chi$ \Alt{} $\xi \oplus c$ \Alt{} $c \oplus \xi$ \Alt{} $\ominus \xi$ \Alt{} $(\xi)$ \Alt{} $\xi \oplus \xi$ \\
\Rule{layout}              & $l$       & \is{}  & $c^{int}$ \\
\Rule{unary operator}      & $\ominus$ & $\in$  & $\lbrace*,\&,+,-,!,\sim\rbrace$ \\
\Rule{binary operator}     & $\oplus$  & $\in$  & $\lbrace*,/,\%,+,-,\ll,\gg,\&,\wedge,|,$ \\
                           &           &        & $<,\leq,>,\geq,=,\neq,\&\&,||\rbrace$ \\
\Rule{type-id}             & $\tau$    &        & C++\cite[\textsection A.7]{C++0x} \\
\Rule{statement}           & $s$       &        & C++\cite[\textsection A.5]{C++0x} \\
\Rule{expression}          & $e^\tau$  &        & C++\cite[\textsection A.4]{C++0x} \\
\Rule{constant-expression} & $c^\tau$  &        & C++\cite[\textsection A.4]{C++0x} \\
\Rule{identifier}          & $x^\tau$  &        & C++\cite[\textsection A.2]{C++0x} \\
\end{tabular}
\end{center}

\noindent                           
{\bf Match statement} is an analog of a switch statement that allows case 
clauses to be used as its case statements. We require it to be terminated with a 
dedicated \code{EndMatch} macro, to properly close the syntactic structure 
introduced with \code{Match} and followed by \code{Case},\code{Qua} and 
\code{Otherwise} macros. Match statement will accept selectors of pointer and 
reference types, treating them uniformly in case clauses. This means that user 
does not have to mention \code{*,&} or any of the \code{const,volatile}-qualifiers
when specifying target types. Passing \code{nullptr} as a selector is considered 
\emph{ill-formed} however -- a choice we have made for performance reasons. 
Examples of match statement has already been presented in 
\textsection\ref{sec:intro} and \textsection\ref{sec:xmpl}.

We support three kinds of {\bf case clauses}: \code{Case}-\emph{clause}, 
\code{Qua}-\emph{clause} and \code{Otherwise}-\emph{clause} also called 
\emph{default clause}. \code{Case} and \code{Qua} clauses are refutable and both 
take a target expression as their first argument. \code{Otherwise} clause is 
irrefutable and can occur at most once among the clauses. Its target type is 
the selector type. \code{Case} and \code{Otherwise} clauses take additionally a 
list of identifiers that will be treated as variable patterns implicitly 
introduced into the clause's scope and bound to corresponding members of their 
target type. \code{Qua} clause permits nested patterns as its arguments, but 
naturally requires all the variables used in the patterns to be explicitly 
pre-declared. Even though our default clause is not required to be the last 
clause of the match statement, we strongly encourage the user to place it 
last (hence the choice of name -- otherwise). Placing it at the beginning or in 
the middle of a match statement will only work as expected with \emph{tagged 
class} and \emph{discriminated union} encodings that use 
\emph{the-only-fit-or-default} strategy for choosing cases. The 
\emph{polymorphic base class} encoding uses \emph{first-fit} strategy and thus 
irrefutable default clause will effectively hide all subsequent case 
clauses, making them redundant. As we show in \textsection\ref{} the switch 
between \emph{polymorphic base class} and \emph{tagged class} encodings can 
simply be made with addition or removal a single definition, which may 
inadvertently change semantics of those match statements, where the default 
clause were not placed last.

When default clause takes optional variable patterns, it behaves in 
exactly the same way as \code{Case} clause whose target type is the selector 
type.

{\bf Target expression} used by the case clauses can be either a target type, 
a constant value, representing \emph{layout}~\textsection\ref{sec:bnd} or a 
\emph{view} type combining the two~\textsection\ref{sec:view}. Constant value 
is only allowed for discriminated union encoding of algebraic data types, in 
which case the library assumes the target type to be the selector type.

{\bf Views} in our library are represented by instantiations of a template class 
\code{view<T,l>} that takes a target type and a layout, combining the two into a 
new type. Our library takes care of transparent handling this new type as the 
original combination of target type and layout. Views are discussed in details 
in~\textsection\ref{sec:view}.

{\bf Match expression} can be seen as an inline version of match statement with 
a single \code{Qua} clause. Once a pattern is created, it can be applied to an 
expression in order to check whether that expression matches the pattern, 
possibly binding some variables in it. The result of application is always of 
type \code{bool} except for the tree pattern, where it is a value convertible to 
\code{bool}. The actual value in this case is going to be a pointer to target 
type \code{T} in case of a successful match and a \code{nullptr} otherwise. 
Match expressions will most commonly be seen to quickly decompose a possibly 
nested expression with a tree pattern as seen in the example in the paragraph 
below. They are the most used expressions under the hood however that let our 
library be composable. 

{\bf Pattern} summarizes \emph{applicative patterns} -- patterns that can be 
used in a match expression described above. For convenience reasons this 
category is extended with $c$ and $x$ to form an {\bf extended pattern} -- a
pattern that can be used as an argument of \emph{tree pattern} and \code{Qua} 
clause. Extended pattern lets us use constants as a \emph{value pattern} and 
regular C++ variables as a \emph{variable pattern} inside these constructs. The 
library implicitly recognizes them and transforms into $\varsigma$ and $\iota$ 
respectively. This transformation is further explained in~\textsection\ref{sec:aux} 
with $\stackrel{flt}{\vdash}$ rule set.

{\bf Tree pattern} takes a target type and an optional layout as its template 
arguments, which uniquely determines a concrete decomposition scheme for the 
type. Any nested sub-patterns are taken as run-time arguments. Besides 
applicative patterns, we allow constants and regular C++ variables to be passed 
as arguments to a tree pattern. They are treated as \emph{value patterns} and 
\emph{variable patterns} respectively. Tree patterns can be arbitrarily nested. 
The following example reimplements \code{factorize} from 
\textsection\ref{sec:bg} in C++ enhanced with our SELL:

\begin{lstlisting}
const Expr* factorize(const Expr* e)
{
    const Expr *e1, *e2, *e3, *e4;
    if (match<Plus>(match<Times>(e1,e2),match<Times>(e3,e4))(e))
        if (e1 == e3)
            return new Times(e1, new Plus(e2,e4));
        else
        if (e2 == e4)
            return new Times(new Plus(e1,e3), e4);
    return e;
}
\end{lstlisting}

\noindent
The above example instantiates a nested pattern and then immediately applies it 
to value \code{e} to check whether the value matches the pattern. If it does, 
it binds local variables to sub-expressions, making them available inside if.
Examples like this are known to be a week spot of visitor design pattern and we 
invite you to implement it with it in order to compare both solutions.

{\bf Guard patterns} in our SELL consist of two expressions separated by operator 
\code{|=}\footnote{Operator \code{|=} defining the guard was chosen arbitrarily 
from those that have relatively low precedence in C++. This was done to allow 
most of the other operators be used inside the condition without parenthesis}: 
an expression being matched (left operand) and a condition (right operand). The 
right operand is allowed to make use of the variable bound in the left operand. 
When used on arguments of a tree pattern, the condition is also allowed to make 
use of any variables bound by preceding argument positions. Naturally, a guard 
pattern that follows a tree pattern may use all the variables bound by the tree 
pattern. Consider for example decomposition of a color value, represented as a 
three-byte RGB triplet:

\begin{lstlisting}[keepspaces,columns=flexible]
variable<double> r,g,b;
auto p = match<RGB>( 
             255*r, 
             255*g |= g [<] r, 
             255*b |= b [<] g+r
         ) |= r+g+b <= 0.5;
\end{lstlisting}

Note that C++ standard leaves the order of evaluation of functions arguments 
unspecified\cite[\textsection 8.3.6]{C++0x}, while we seem to rely here on 
\emph{left-to-right} order. The reason we can do this lays in the fact that for 
the purpose of pattern matching all the sub-expressions are evaluated lazily and 
the unspecified order of evaluation refers only to the order in which 
corresponding expression templates are created. The actual evaluation of these 
expression templates happens later when the pattern is applied to an expression 
and since at that point we have an entirely built expression at hand, we 
ourselves enforce its evaluation order.

Another important bit about our guards that has to be kept in mind is that 
guards depend on lazy evaluation and thus expression templates. This is why the 
variables mentioned inside a guard pattern must be of type \code{variable<T>} 
and not just \code{T}. Failing to declare them as such will result in eager 
evaluation of guard expression as a normal C++ expression. This will usually go 
unnoticed at compile time, while surprising at run time, especially to novices.

We chose to provide a syntax for guards to be specified on arguments of a tree 
pattern in addition to after the pattern in order to detect mismatches early 
without having to compute and either bind or match subsequent arguments.

{\bf n+k pattern} is essentially a subset of \emph{xt expressions} with at most 
one non-repeated variable in them. This allows for expressions like $2x+1$, but 
not for $x+x+1$, which even though is semantically equivalent to the first one, 
will not be accepted by our library as an \emph{n+k pattern}.

Expressions \code{255*r}, \code{255*g} and \code{255*b} in the example above 
were instances of our \emph{generalized n+k patterns}. Informally they meant the 
following: the value we are matching against is of the form $255*x$, what is the 
value of $x$? Since color components were assumed to be byte values in the range 
$\left[0-255\right]$ the user effectively gets normalized RGB coordinates in 
variables \code{r}, \code{g} and \code{b} ranging over $\left[0.0-1.0\right]$.

n+k pattern are visually appealing in the sense that they let us write code very 
close mathematical notations often used in literature. Consider the definition 
of fast Fibonacci algorithm taken almost verbatim from the book. Function 
\code{sqr} here returns a square of its argument.

\begin{lstlisting}
int fib(int n)
{
    variable<int> m;
    if (match<int>(1)(n))     return 1;
    if (match<int>(2)(n))     return 1;
    if (match<int>(2*m)(n))
        return sqr(fib(m+1)) - sqr(fib(m-1));
    if (match<int>(2*m+1)(n))
        return sqr(fib(m+1)) + sqr(fib(m));
}
\end{lstlisting}

{\bf Wildcard pattern} in our library is represented by a predefined global 
variable \code{_} of a dedicated type \code{wildcard} bearing no state. 
Wildcard pattern is accepted everywhere where a \emph{variable pattern} $\chi$ 
is accepted. The important difference from a use of an unused variable is that 
no code is executed to obtain a value for a given position and copy that value 
into a variable. The position is ignored altogether and the pattern matching 
continues.

There are two kinds of {\bf variable patterns} in our library: \emph{xt variable} 
and \emph{xt reference}. {\bf xt variable} stands for \emph{expression-template 
variable} and refers to variables whose type is \code{variable<T>} for any given 
type \code{T}. {\bf xt reference} is an \emph{expression-template variable 
reference} whose type is \code{var_ref<T>}. The latter is never declared 
explicitly, but is implicitly introduced by the library to wrap regular 
variables in places where our syntax accepts $x$. Both variable kinds are 
terminal symbols in our SELL letting us build expression templates of them. The 
main difference between the two is that {\bf xt variable} $\kappa$ maintains a 
value of type \code{T} as its own state, while {\bf xt reference} $\iota$ only 
keeps a reference to a user-declared variable of type \code{T}. Besides the 
difference in where the state is stored, both kinds of variables have the same 
semantics and we will thus refer to them as $\chi$. We will also use $\chi^\tau$ 
to mean either $\kappa^{variable\langle\tau\rangle}$ or 
$\iota^{var\_ref\langle\tau\rangle}$ since the type of the actual data $\tau$ is 
what we are interested in, while the fact that it was wrapped into 
\code{variable<>} or \code{var_ref<>} can be implicitly inferred from the 
meta-variable $\chi$. We would also like to point out that in most cases a 
variable pattern can be used as regular variable in the same context where a 
variable of type \code{T} can. In few cases where this does not happen 
implicitly, the user might need to put an explicit cast to \code{T&} or 
\code{const T&}.

{\bf Value pattern} is similarly never declared explicitly and is implicitly 
introduced by the library in places where $c$ is accepted.

{\bf xt expression} refers to an \emph{expression-template expression} -- a 
non-terminal symbol in our expression language built by applying a given 
operator to argument expression templates. We use this syntactic category to 
distinguish lazily evaluated expressions introduced by our SELL from eagerly 
evaluated expressions, directly supported by C++.

{\bf Layout} is an enumerator that user can use to define alternative bindings 
for the same class. When layout is not mentioned, the default layout is used, 
which is the only required layout a user has to define if she wishes to make use 
of bindings. We discuss layouts in details in \textsection\ref{sec:bnd}.

{\bf Binary operator} and {\bf unary operator} name a subset of C++ operators we 
make use of and provide support for in our pattern-matching library. 

The remaining syntactic categories refer to non-terminals in the C++ grammar 
bearing the same name. {\bf Identifier} will only refer to variable names in our 
SELL, even though it has a broader meaning in the C++ grammar. {\bf Expression}
subsumes any valid C++ expression. We use expression $e^\tau$ to refer to a C++ 
expression, whose result type is $\tau$. {\bf Constant-expression} is a subset 
of the above restricted to only expression computable at compile time. {\bf 
Statement} refers to any valid statement allowed by the C++ grammar. Our match 
statement $M$ would have been extending this grammar rule with an extra case 
should it have been defined in the grammar directly. {\bf Type-id} represents a 
type expression that designates any valid C++ type. We are using this 
meta-variable in the superscript to other meta-variables in order to indicate a 
C++ type of the entity they represent.

\subsection{Semantics}
\label{sec:sem}

We use natural semantics\cite{Kahn87} (big-step operational semantics) to 
describe our pattern-matching semantics. As with syntax, we do not formalize the 
semantics of the entire language, but concentrate only on presenting relevant 
parts of our extension. We assume the entire state of the program is modeled by 
an environment $\Gamma$, which we can query as $\Gamma(x)$ to get a value of a 
variable $x$. In addition to meta-variables we have seen already, metavariables 
$u,v$ and $b^{bool}$ range over values. We make a simplifying assumption that 
all values of user-defined types are represented via variables of reference 
types and there exist a non-throwing operation \DynCast{\tau}{v} that can test 
whether an object of a given type is an instance of another type, returning a 
proper reference to it or a dedicated value \nullptr{} that represents 
\code{nullptr}. Intuitively, the semantics of such references is that of 
pointers in C++, which are implicitly dereferenced. We describe our semantics 
with several rule sets that deal with different parts of our syntax.

\subsubsection{Semantics of Matching Expressions}
\label{sec:semme}

Our first rule set deals with pattern application $\pi(e)$, which essentially 
performs matching of a pattern $\pi$ against expression $e$. The judgements are of 
the form $\Gamma\vdash \pi(e) \evals v,\Gamma'$ that can be interpreted as given 
an environment $\Gamma$, pattern application $\pi(e)$ results in value $v$ and 
environment $\Gamma'$. When we use $\evalspp$ instead of $\evals$ we simply 
pointing out that corresponding evaluation rule comes from the C++ semantics and 
not from our rules.

\begin{mathpar}
\inferrule[Wildcard]
{}
{\Gamma\vdash \_(e) \evals true,\Gamma}

\inferrule[Value]
{\Gamma\vdash e \evalspp v,\Gamma_1 \\ \Gamma_1\stackrel{eval}{\vdash} \varsigma \evals u,\Gamma_2}
{\Gamma\vdash \varsigma^\tau(e^\tau) \evals (u==v),\Gamma_2}

\inferrule[Variable]
{\Gamma\vdash e \evalspp v,\Gamma_1 \\ \Gamma_1 \vdash \DynCast{\tau_1}{v} \evalspp u,\Gamma_2}
{\Gamma\vdash \chi^{\tau_1}(e^{\tau_2}) \evals (u \neq \nullptr{}),\Gamma_2[\chi\leftarrow u]}
\end{mathpar}

\begin{mathpar}
\inferrule[n+k Binary Left]
{\Gamma\vdash e \evalspp v_1,\Gamma_1 \\ \Gamma_1\vdash \Psi_\oplus^\tau[v_1](\bullet,c) \evalspp \langle b_2,v_2\rangle,\Gamma_2 \\ \Gamma_2\vdash \eta(v_2) \evals b_3,\Gamma_3}
{\Gamma\vdash (\eta^\tau \oplus c)(e) \evals (b_2 \wedge b_3),\Gamma_3}
\end{mathpar}

\begin{mathpar}
\inferrule[n+k Binary Right]
{\Gamma\vdash e \evalspp v_1,\Gamma_1 \\ \Gamma_1\vdash \Psi_\oplus^\tau[v_1](c,\bullet) \evalspp \langle b_2,v_2\rangle,\Gamma_2 \\ \Gamma_2\vdash \eta(v_2) \evals b_3,\Gamma_3}
{\Gamma\vdash (c \oplus \eta^\tau)(e) \evals (b_2 \wedge b_3),\Gamma_3}
\end{mathpar}

\begin{mathpar}
\inferrule[n+k Unary]
{\Gamma\vdash e \evalspp v_1,\Gamma_1 \\ \Gamma_1\vdash \Psi_\ominus^\tau[v_1](\bullet)  \evalspp \langle b_2,v_2\rangle,\Gamma_2 \\ \Gamma_2\vdash \eta(v_2) \evals b_3,\Gamma_3}
{\Gamma\vdash (\ominus \eta^\tau)(e) \evals (b_2 \wedge b_3),\Gamma_3}
\end{mathpar}

\begin{mathpar}
\inferrule[Guard]
{\Gamma\vdash e \evalspp v_1,\Gamma_1 \\ \Gamma_1\vdash \pi(v_1) \evals b_2,\Gamma_2 \\ \Gamma_2\stackrel{eval}{\vdash} \xi \evals b_3,\Gamma_3}
{\Gamma\vdash (\pi \models \xi)(e) \evals (b_2 \wedge b_3),\Gamma_3}
\end{mathpar}

\begin{mathpar}
\inferrule[Tree-Nullptr]
{\Gamma \vdash e \evalspp v,\Gamma_0 \\ \Gamma_0 \vdash \DynCast{\tau}{v} \evalspp \nullptr{},\Gamma_1}
{\Gamma\vdash ($match$\langle\tau\left[,l\right]\rangle(\omega_1,...,\omega_k))(e) \evals \nullptr{},\Gamma_1}
\end{mathpar}

\begin{mathpar}
\inferrule[Tree-False]
{\Gamma \vdash e \evalspp v,\Gamma_0 \\ \Gamma_0 \vdash \DynCast{\tau}{v} \evalspp u^{\tau},\Gamma_1 \\\\
 \Gamma_1    \vdash \Delta_1    ^{\tau,l}(u) \evalspp v_1,    \Gamma_1'     \\ \Gamma_1'    \stackrel{flt}{\vdash} \omega_1     \evals \pi_1    \\ \Gamma_1'    \vdash \pi_1(v_1)         \evals true, \Gamma_2     \\\\
 \Gamma_2    \vdash \Delta_2    ^{\tau,l}(u) \evalspp v_2,    \Gamma_2'     \\ \Gamma_2'    \stackrel{flt}{\vdash} \omega_2     \evals \pi_2    \\ \Gamma_2'    \vdash \pi_2(v_2)         \evals true, \Gamma_3     \\\\
 \cdots \\\\
 \Gamma_{i-1}\vdash \Delta_{i-1}^{\tau,l}(u) \evalspp v_{i-1},\Gamma_{i-1}' \\ \Gamma_{i-1}'\stackrel{flt}{\vdash} \omega_{i-1} \evals \pi_{i-1}\\ \Gamma_{i-1}'\vdash \pi_{i-1}(v_{i-1}) \evals true, \Gamma_i     \\\\
 \Gamma_i    \vdash \Delta_i    ^{\tau,l}(u) \evalspp v_i,    \Gamma_i'     \\ \Gamma_i'    \stackrel{flt}{\vdash} \omega_i     \evals \pi_i    \\ \Gamma_i'    \vdash \pi_i(v_i)         \evals false,\Gamma_{i+1} \\\\
}
{\Gamma\vdash ($match$\langle\tau\left[,l\right]\rangle(\omega_1,...,\omega_k))(e) \evals \nullptr{},\Gamma_{i+1}}
\end{mathpar}

\begin{mathpar}
\inferrule[Tree-True]
{\Gamma \vdash e \evalspp v,\Gamma_0 \\ \Gamma_0 \vdash \DynCast{\tau}{v} \evalspp u^{\tau},\Gamma_1 \\\\
 \Gamma_1    \vdash \Delta_1    ^{\tau,l}(u) \evalspp v_1,    \Gamma_1'     \\ \Gamma_1'    \stackrel{flt}{\vdash} \omega_1     \evals \pi_1    \\ \Gamma_1'    \vdash \pi_1(v_1)         \evals true, \Gamma_2     \\\\
 \Gamma_2    \vdash \Delta_2    ^{\tau,l}(u) \evalspp v_2,    \Gamma_2'     \\ \Gamma_2'    \stackrel{flt}{\vdash} \omega_2     \evals \pi_2    \\ \Gamma_2'    \vdash \pi_2(v_2)         \evals true, \Gamma_3     \\\\
 \cdots \\\\
%\Gamma_{k-1}\vdash \Delta_{k-1}^{\tau,l}(u) \evalspp v_{k-1},\Gamma_{k-1}' \\ \Gamma_{k-1}'\stackrel{flt}{\vdash} \omega_{k-1} \evals \pi_{k-1}\\ \Gamma_{k-1}'\vdash \pi_{k-1}(v_{k-1}) \evals true, \Gamma_k     \\\\
 \Gamma_k    \vdash \Delta_k    ^{\tau,l}(u) \evalspp v_k,    \Gamma_k'     \\ \Gamma_k'    \stackrel{flt}{\vdash} \omega_k     \evals \pi_k    \\ \Gamma_k'    \vdash \pi_k(v_k)         \evals true, \Gamma_{k+1} \\\\
}
{\Gamma\vdash ($match$\langle\tau\left[,l\right]\rangle(\omega_1,...,\omega_k))(e) \evals u^{\tau},\Gamma_{i+1}}
\end{mathpar}

Matching a wildcard pattern against expression always succeeds without changes 
to the environment (\RefTirName{Wildcard}). Matching a value pattern against 
expression succeeds only if the result of evaluating that expression is the same 
as the constant (\RefTirName{Value}). Matching against variable will always 
succeeds when the type of expression $e$ is the same as variable's target type 
$\tau$. When the types are different, the library will try to use 
\code{dynamic_cast<}$\tau$\code{>(e)} to see whether dynamic type of expression can 
be casted to $\tau$. If it does, matching succeeds, binding variable to the 
result of \code{dynamic_cast}. If it does not, matching fails 
(\RefTirName{Variable}).

Our semantics for generalized n+k patterns draws on the notion of 
\emph{backward collecting semantics} used in \emph{abstract 
interpretation}\cite{CousotCousot92-1}. In general, backward collecting 
semantics $Baexp\Sem{A}(E)R$ of an expression $A$ defines the subset of 
possible environments $E$ such that the expression may evaluate, without 
producing a runtime error, to a value belonging to given set $R$:

\begin{lstlisting}
@$Baexp\Sem{A}(E)R = \{x \in E | A(x) \in R\}$@
\end{lstlisting} 

This can be interpreted as following: given a set $E$ from where the arguments 
of an expression $A$ draw their values, as well as a set $R$ of acceptable (not 
all possible) results, find the largest subset $X \subseteq E$ of arguments that 
will only render results of evaluating $A$ on them in $R$.

Intuitively n+k patterns like $f(x,y)=v$ relate a known result of a given 
function application to its arguments (hence analogy with backward collecting 
semantics). The case where multiple unknown arguments are matched against a 
single result should not be immediately discarded as there are known n-ary 
functions whose inverse is unique. An example of such function is Cantor pairing 
function that defines bijection between $\mathbb{N}\times\mathbb{N}$ and $\mathbb{N}$.
Even when such mappings are not one-to-one, their restriction to a given 
argument often is. Most generalizations of n+k patterns seem to agree on the 
following rules:

\begin{itemize}
\item Absence of solution that would result in a given value should be indicated 
      through rejection of the pattern.
\item Presence of a unique solution should be indicated with acceptance of the 
      pattern and binding of corresponding variables to the solution.
\end{itemize}

\noindent As to the case when multiple solutions are possible, several 
alternatives can be viable:

\begin{itemize}
\item Reject the pattern.
\item Accept, binding to either an arbitrary or some normalized solution.
\item When set of solutions is guaranteed to be finite -- accept, binding 
      solutions to a set variable.
\item When set of solutions is guaranteed to be enumerable -- accept, binding 
      solutions to a generator capable of enumerating them all.
\end{itemize}

\noindent
We believe that depending on application, any of these semantic choices can be 
valid, which is why we prefer not to make such choice for the user, but rather 
provide him with means to decide himself. This is why our semantics for matching 
against generalized n+k pattern depends on a family of user-defined functions 

\begin{lstlisting}
@$\Psi_f^\tau:\tau_r\times\tau_1\times...\times1\times...\times\tau_k\rightarrow bool\times\tau$@
\end{lstlisting} 

\noindent
such that $\Psi_f^\tau[r](c_1,...,\bullet,...,c_k)$ for a given function 

\begin{lstlisting}
@$f:\tau_1,...,\tau,...,\tau_k\rightarrow\tau_r$@
\end{lstlisting} 

\noindent should return a pair composed of a boolean indicating acceptance of a 
pattern $f(c_1,...,x^\tau,...,c_k)=r$ and a solution with respect to $x$ 
when the match was reported successful. Symbol $\bullet$ indicates a position in 
the argument list for which a solution is sought, the rest of the arguments are 
known values. We describe how user can supply the function $\Psi_f^\tau$ for his 
own operation $f$ in \textsection\ref{sec:slv}.

The only difference between the three rules defining semantics of n+k patterns 
is the arity of the root operator and the position in the argument list in which 
the only non-value pattern was spotted (\RefTirName{n+k Binary Left}, 
\RefTirName{n+k Binary Right} and \RefTirName{n+k Unary}). We use user-defined 
$\Psi_f^\tau$ to solve for a given argument of a given operator and then recurse 
to match corresponding sub-expression. Note that when user did not provide 
$\Psi_f^\tau$ for the argument in which solution is sought, the rule is 
rejected.

Evaluation of a guard pattern first tries to match the left hand side of a guard 
expression, usually binding a variable in it, and then if the match was 
successful, lazily evaluates its right hand side to make sure the new value of 
the bound variable is used. The result of evaluation the right hand side 
converted to \code{bool} is reported as the result of matching the entire 
pattern (\RefTirName{Guard}).

Matching of a tree patterns begins with evaluating selector expression and 
casting it dynamically to target type $\tau$ when selector type is not $\tau$. 
When \code{dynamic_cast} fails returning \code{nullptr}, the pattern is rejected 
(\RefTirName{Tree-Nullptr}). Once a value of a target type has been uncovered, 
we proceed with matching arguments left-to-right. For each argument we first 
translate \emph{extended pattern} $\omega$ accepted by tree pattern into an 
\emph{application pattern} $\pi$ to get rid of the syntactic convenience we 
allow on arguments of tree patterns. Using the target type and optional layout 
that was provided by the user, we obtain a value that should be bound in the 
$i^{th}$ position of decomposition. Again we rely on family of user provided 
functions $\Delta_i^{\tau,l}(u)$ that take an object instance and returns a 
value bound in the $i^{th}$ position of its $l^{th}$ layout. Specification of 
function $\Delta$ by the user is discussed in~\textsection\ref{sec:bnd}. Here we 
would like to point out however that the number of argument patterns passed over 
to the tree pattern could be smaller than the number of binding positions defined 
by specific layout. Remaining argument positions are implicitly assumed to be 
filled with the wildcard pattern.

When we have the value for the $i^{th}$ position of object's decomposition, we 
match it against the pattern specified in the $i^{th}$ position and if the value 
is accepted we move on to matching the next argument (\RefTirName{Tree-False}). 
Only in case when all the argument patterns have been successfully matched the 
matching succeeds by returning a pointer to the target type, which in C++ can be 
used everywhere a boolean expression is expected. Returning pointer instead of 
just boolean value gives us functionality similar to that of \emph{as 
patterns} while maintaining the composibility with the 
rest of the library (\RefTirName{Tree-True}).

\subsubsection{Semantics of Match Statement}
\label{sec:semms}

Our second rule set deals with semantics of a \emph{match statement}. The 
judgements are of the form $\Gamma\vdash s \evals u,\Gamma'$ on statements, 
including match statement, and are slightly extended for case clauses 
$\Gamma\vdash_v C \evals u,\Gamma'$ with value $v$ of a selector that is passed 
along from the match statement onto the clauses.

\begin{mathpar}
\inferrule[Match-True]
{\Gamma \vdash e \evalspp v,\Gamma_1 \\ v \neq \nullptr \\
 \Gamma_1    \vdash_v C_1    \evals false,\Gamma_2 \\
 \Gamma_2    \vdash_v C_2    \evals false,\Gamma_3 \\
 \cdots \\
 \Gamma_{i-1}\vdash_v C_{i-1}\evals false,\Gamma_i \\
 \Gamma_i    \vdash_v C_i    \evals true, \Gamma_{i+1} \\
 \Gamma_{i+1}\vdash \vec{s}_i \evalspp u,\Gamma'
}
{\Gamma\vdash Match(e) \left[C_i \vec{s}_i\right]^*_{i=1..n} EndMatch \evals u,\Gamma'$\textbackslash$\{x | x \not\in \Gamma_i\}}
\end{mathpar}

\begin{mathpar}
\inferrule[Match-False]
{\Gamma \vdash e \evalspp v,\Gamma_1 \\ v \neq \nullptr \\
 \Gamma_1    \vdash_v C_1    \evals false,\Gamma_2 \\
 \Gamma_2    \vdash_v C_2    \evals false,\Gamma_3 \\
 \cdots \\
 \Gamma_{n-1}\vdash_v C_{n-1}\evals false,\Gamma_n \\
 \Gamma_n    \vdash_v C_n    \evals false,\Gamma_{n+1}
}
{\Gamma\vdash Match(e) \left[C_i \vec{s}_i\right]^*_{i=1..n} EndMatch \evals false,\Gamma_{n+1}}
\end{mathpar}

\begin{mathpar}
\inferrule[Qua-Type]
{\Gamma \vdash $match$\langle\tau\rangle(\vec{\omega})(v) \evals u,\Gamma' \\
 \Gamma'' = (u \neq \nullptr\ ?\ \Gamma'[$matched$^\tau\rightarrow u] : \Gamma')}
{\Gamma \vdash_v        Qua(\tau,\vec{\omega}) \evals u,\Gamma''}
\end{mathpar}

\begin{mathpar}
\inferrule[Qua-Layout]
{\Gamma \vdash $match$\langle\tau,l\rangle(\vec{\omega})(v) \evals u,\Gamma' \\
 \Gamma'' = (u \neq \nullptr\ ?\ \Gamma'[$matched$^\tau\rightarrow u] : \Gamma')}
{\Gamma \vdash_{v^\tau} Qua(l,\vec{\omega})    \evals u,\Gamma''}
\end{mathpar}

\begin{mathpar}
\inferrule[Qua-View]
{\Gamma \vdash $match$\langle\tau,l\rangle(\vec{\omega})(v) \evals u,\Gamma' \\
 \Gamma'' = (u \neq \nullptr\ ?\ \Gamma'[$matched$^\tau\rightarrow u] : \Gamma')}
{\Gamma \vdash_v        Qua(view\langle\tau,l\rangle,\vec{\omega}) \evals u,\Gamma''}
\end{mathpar}

\begin{mathpar}
\inferrule[Case-Type]
{\Delta_i^{\tau} : \tau \rightarrow \tau_i, i=1..k \\
 \Gamma[x_i^{\tau_i}\rightarrow\tau_i()]_{i=1..k} $match$\langle\tau\rangle(x_1,...,x_k)(v) \evals u,\Gamma' \\
 \Gamma'' = (u \neq \nullptr\ ?\ \Gamma'[$matched$^\tau\rightarrow u] : \Gamma'$\textbackslash$\{x_i | i=1..k\})}
{\Gamma \vdash_v Case(\tau,x_1,...,x_k) \evals u,\Gamma''}
\end{mathpar}

\begin{mathpar}
\inferrule[Case-Layout]
{\Delta_i^{\tau,l} : \tau \rightarrow \tau_i, i=1..k \\
 \Gamma[x_i^{\tau_i}\rightarrow\tau_i()]_{i=1..k} $match$\langle\tau,l\rangle(x_1,...,x_k)(v) \evals u,\Gamma' \\
 \Gamma'' = (u \neq \nullptr\ ?\ \Gamma'[$matched$^\tau\rightarrow u] : \Gamma'$\textbackslash$\{x_i | i=1..k\})}
{\Gamma \vdash_{v^\tau} Case(l,x_1,...,x_k) \evals u,\Gamma''}
\end{mathpar}

\begin{mathpar}
\inferrule[Case-View]
{\Delta_i^{\tau,l} : \tau \rightarrow \tau_i, i=1..k \\
 \Gamma[x_i^{\tau_i}\rightarrow\tau_i()]_{i=1..k} $match$\langle\tau,l\rangle(x_1,...,x_k)(v) \evals u,\Gamma' \\
 \Gamma'' = (u \neq \nullptr\ ?\ \Gamma'[$matched$^\tau\rightarrow u] : \Gamma'$\textbackslash$\{x_i | i=1..k\})}
{\Gamma \vdash_v Case(view\langle\tau,l\rangle,x_1,...,x_k) \evals u,\Gamma''}
\end{mathpar}

\begin{mathpar}
\inferrule[Otherwise]
{\Gamma \vdash Case(\tau,\vec{x})(v) \evals true,\Gamma'}
{\Gamma \vdash_{v^\tau} Otherwise(\vec{x}) \evals true,\Gamma'}
\end{mathpar}

Evaluation of a match statement begins with evaluation of selector expression, 
which is not allowed to result in \code{nullptr}. This value is passed along to 
each of the clauses. The clauses are evaluated in their lexical order until the
first one that is not rejected. Statements associated with it are evaluated to 
form the outcome of the match statement. The resulting environment makes sure 
that local variables introduced by case clauses are not available after the 
match statement (\RefTirName{Match-True}). When none of the clauses were 
accepted, which is only possible when default clause was not specified, the 
resulting environment might still be different from the initial environment 
because of variables bound in partial matches during evaluation of clauses 
(\RefTirName{Match-False}).

Evaluation of a \code{Qua}-clause with a type is equivalent to evaluation of a 
corresponding match expression on a tree pattern (\RefTirName{Qua-Type}). The 
same happens when evaluating \code{Qua}-clause with layout, but now selector 
type is used as target type of the tree pattern as well as layout is passed 
over (\RefTirName{Qua-Layout}). Similarly, \code{Qua}-clause with a view passes 
target type and layout from the view into corresponding matching expression 
(\RefTirName{Qua-View}). In all three cases, \code{Qua}-clause will introduce a 
variable \code{matched} of type $\tau\&$ that is bound to selector properly 
casted to the target type $\tau$ into the local scope of the clause.

Similarly to rules for \code{Qua}-clause, the three rules for \code{Case}-clause 
only differ between themselves on the form of the target expression. Evaluation 
of the \code{Case}-clause begins with lookup for each of its $k$ arguments 
following target expression, the type of the value returned in the position $i$. 
Environment is then extended with default-initialized variables of those types. 
In practice, the variables are of reference type bound to either temporary or 
reference returned by $\Delta_i^{\tau,l}(u)$ so that no unnecessary copying is 
happening. A matching expression on a tree pattern is then executed to determine 
the acceptance of \code{Case}-clause. In case of success, the resulting 
environment will be augmented with locally bound variables passed as arguments 
as well as variable \code{matched} described above. In case of failure, the 
resulting environment might again contain the side-effects of partial matching, 
but will not introduce new variables into the environment (\RefTirName{Case-Type}, 
\RefTirName{Case-Layout} and \RefTirName{Case-View}).

Evaluation of default clause cannot fail because there is no \code{dynamic_cast} 
involved neither for the selector nor for implicit local variables: for the 
former the target type is by definition the selector type, while for the latter 
the type is chosen to be the type of expected values (\RefTirName{Otherwise}).

\subsubsection{Auxiliary Rules}
\label{sec:aux}

The next rule set deals with evaluation of expression templates referred to 
from the previous rule sets via $\stackrel{eval}{\vdash}$. The judgements are of 
the form $\Gamma\vdash \xi \evals v,\Gamma'$ that can be interpreted as given an 
environment $\Gamma$, evaluation of an expression template $\xi$ results in value 
$v$ and environment $\Gamma'$. We refer here to an unspecified semantic function 
$\Sem{o}$ that represents C++ semantics of operation $o$ as specified by the C++ 
standard.

\begin{mathpar}
\inferrule[Var]
{}
{\Gamma\vdash \chi \evals \Gamma(\chi),\Gamma}

\inferrule[Unary]
{\Gamma\vdash \xi \evals v,\Gamma_1}
{\Gamma\vdash \ominus \xi \evals \Sem{\ominus} v,\Gamma_1}

\inferrule[Binary]
{\Gamma\vdash \xi_1 \evals v_1,\Gamma_1 \\ \Gamma_1\vdash \xi_2 \evals v_2,\Gamma_2}
{\Gamma\vdash \xi_1 \oplus \xi_2 \evals v_1\Sem{\oplus}v_2,\Gamma_2}

\inferrule[Binary-Left]
{\Gamma\vdash \xi \evals v,\Gamma_1}
{\Gamma\vdash \xi \oplus c \evals v\Sem{\oplus}c,\Gamma_1}

\inferrule[Binary-Right]
{\Gamma\vdash \xi \evals v,\Gamma_1}
{\Gamma\vdash c \oplus \xi \evals c\Sem{\oplus}v,\Gamma_1}
\end{mathpar}

The rules are quite simple so we do not elaborate them in details. The reason we 
have two separate rules for the case when one of the arguments is constant 
expression stems from the idiomatic use of expression templates enabling direct 
use of constants in operations that already involve expression template 
arguments.

The next set of rules describes transformation of extended patterns into 
applicative patterns to get rid of syntactic sugar enabled by extended patterns. 

\begin{mathpar}
\inferrule[Filter-Pattern]
{}
{\Gamma\stackrel{flt}{\vdash} \pi \evals \pi}

\inferrule[Filter-Variable]
{}
{\Gamma\stackrel{flt}{\vdash} x \evals \iota(x)}

\inferrule[Filter-Constant]
{}
{\Gamma\stackrel{flt}{\vdash} c \evals \varsigma(c)}
\end{mathpar}

\subsection{Bindings Syntax}
\label{sec:bnd}

Structural decomposition in functional languages is done with the help of 
constructor symbol and a list of patterns in positions that correspond to 
arguments of that constructor. C++ allows for multiple constructors in a class, 
often overloaded for different types but the same arity. Implicit nature of 
variable patterns that matches ``any value'' will thus not help in 
disambiguating such constructors, unless the user explicitly declares the 
variables, thus fixing their types. Besides, C++ does not have means for 
general compile-time reflection, so a library like ours cannot enumerate 
all the constructors present in a class automatically. This is why we decided to 
separate \emph{construction} of objects from their \emph{decomposition} through 
pattern matching with \emph{bindings}.

%Similarly to constructors, a class may have multiple deconstructors. Unlike 
%constructors, deconstructors are named differently.

The following grammar defines a syntax for a sublanguage our user will use to 
specify decomposition of various classes for pattern matching:\footnote{We reuse 
several meta-variables introduced in the previous grammar}

\begin{center}
\begin{tabular}{rp{0em}cl}
\Rule{bindings}                &           & \is{}  & $\delta^*$ \\
\Rule{binding definition}      & $\delta$  & \is{}  & \code{template <}$\left[\vec{p}\right]$\code{>} \\
                               &           &        & \code{struct bindings<} $\tau[$\code{<}$\vec{p}$\code{>}$]\left[,l\right]$\code{>} \\
                               &           &        & \code{\{} $\left[ks\right]\left[kv\right]\left[bc\right]\left[cm^*\right]$ \code{\};} \\
\Rule{class member}            & $cm$      & \is{}  & \code{CM(}$c^{size\_t},q$\code{);} \\
\Rule{kind selector}           & $ks$      & \is{}  & \code{KS(}$q$\code{);}    \\
\Rule{kind value}              & $kv$      & \is{}  & \code{KV(}$c$\code{);}    \\
\Rule{base class}              & $bc$      & \is{}  & \code{BC(}$\tau$\code{);} \\
\Rule{template-parameter-list} & $\vec{p}$ &        & C++\cite[\textsection A.12]{C++0x} \\
\Rule{qualified-id}            & $q$       &        & C++\cite[\textsection A.4]{C++0x} \\
\end{tabular}
\end{center}

Any given class $\tau$ may have an arbitrary amount of {\bf bindings} associated 
with it. These bindings are distinguished through the \emph{layout} parameter 
$l$, with \emph{default binding} having the possibility to omit it entirely. 
Default binding is implicitly associated with layout whose value is equal to 
predefined constant \code{default_layout = size_t(}$\sim$\code{0)}. User-defined 
layouts should not reuse this dedicated value.

{\bf Binding definition} consists of either full or partial specialization of a 
template-class:

\begin{lstlisting}
template <typename T, size_t l = default_layout>
    struct bindings;
\end{lstlisting}

\noindent
The body of the class should consist of optional \code{KS} and \code{KV} 
specifiers as well as a sequence of \code{CM} specifiers. These specifiers 
generate the necessary definitions for querying bindings by the library code.

{\bf Class Member} specifier \code{CM(}$c,q$\code{)} that takes (zero-based) binding 
position $c$ and a qualified identifier $q$, specifies a member, whose value will 
be used to bind variable in position $c$ of $\tau$'s decomposition with this 
\emph{binding definition}. Qualified identifier is allowed to be of one of the 
following kinds:

\begin{itemize}
\item Data member of the target type
\item Nullary member-function of the target type
\item Unary external function taking the target type by pointer, reference or value.
\end{itemize}

\noindent
The following example definition provides bindings to the standard library type 
\code{std::complex<T>}:

\begin{lstlisting}[keepspaces,columns=flexible]
template <typename T> struct bindings<std::complex<T>> {
    CM(0, std::complex<T>::real); 
    CM(1, std::complex<T>::imag); 
};
\end{lstlisting}

\noindent
It states that when pattern matching against \code{std::complex<T>} for any 
given type \code{T}, use the result of invoking member-function \code{real()} to 
obtain the value for the first pattern matching position and \code{imag()} for 
the second position. 

In the presence of several overloaded members with the same name but different 
arity, \code{CM} will unambiguously pick one that falls into one of the three 
listed above categories of accepted members. In the example above, nullary 
\code{T std::complex<T>::real() const} is preferred to unary 
\code{void std::complex<T>::real(T)}.

Note that the binding definition above is made once for all instantiations of 
\code{std::complex} and can be fully or partially specialized for cases of 
interest. Non-parameterized classes will fully specialize the \code{bindings} 
trait to define their own bindings.

Using \code{CM} specifier a user defines the family of function 
$\Delta_i^{\tau,l},i=1..k$ we introduced in \textsection\ref{sec:semme} as 
following:

\begin{lstlisting}
template <> struct bindings<@$\tau$@> {
    CM(0, @$\tau$@::member_for_position_0); 
    ...
    CM(k, @$\tau$@::member_for_position_k); 
};
\end{lstlisting}

Note that binding definitions made this way are \emph{non-intrusive} since the 
original class definition is not touched. They also respect \emph{encapsulation} 
since only the public members of the target type will be accessible from within 
\code{bindings} specialization.

{\bf Kind Selector} specifier \code{KS(}$q$\code{)} is used to specify a member 
of the selector type that will uniquely identify the variant for \emph{Tag 
Class} and \emph{Discriminated Union} encodings. The member $q$ can be of any of 
the three categories listed for \code{CM}, but is required to return an 
\emph{integral type}.

{\bf Kind Value} specifier \code{KV(}$c$\code{)} is used by variant classes 
(encoded as either \emph{Tag Class} or \emph{Discriminated Union}) to specify a 
constant $c$ that uniquely identifies the variant.

{\bf Base Class} specifier \code{BC(}$\tau$\code{)} is used by the taged class 
encoding to specify an immediate base class of the class whose bindings we 
define. A helper specifier \code{BCS(}$\tau*$\code{)} can also be used to 
specify the exact topologically sorted list of base classes 
(\textsection\ref{sec:cotc})

{\bf Layout} parameter $l$, as we mentioned, can be used to define multiple 
bindings to the same target type. This is particularly essential for 
\emph{Discriminated Union} encoding where the types of the variants are the same 
as the type of selector and thus layouts become the only way to associate 
variants with position bindings. For this reason we require binding definitions 
for \emph{Discriminated Union} encoding always use the same constant $l$ as a 
kind value specified with \code{KV(l)} and the layout parameter $l$!

%The above definition will fall short, however, when we have to define bindings 
%for an algebraic data type encoded as \emph{discriminated union}. In this case 
%we have a single target type and multiple bindings associated with it. To 
%account for this, we recognize that a class (whether discriminated union or not)
%may have alternative bindings associated with it and thus introduce an optional 
%integral parameter called \emph{layout} that can be passed to \code{bindings} to
%distinguish various binding layouts. Classes that are not instances of our 
%discriminated union encoding are free to choose whatever unique constants they 
%feel appropriate to define alternative layouts. We require, however, that classes 
%representing discriminated union encoding use constants that correspond to kinds 
%supported by the union and only access members within layout that are valid for 
%its kind. 

Consider for example the following discriminated union describing various 
shapes:

\begin{lstlisting}[keepspaces,columns=flexible]
struct cloc { double first; double second; };
struct ADTShape
{
    enum shape_kind {circle, square, triangle} kind;
    union {
      struct { cloc center;     double radius; }; // circle
      struct { cloc upper_left; double size; };   // square
      struct { cloc first, second, third; };      // triangle
    };
};

template <> struct bindings<ADTShape> { 
    KS(ADTShape::kind);     // Kind Selector
};
template <> struct bindings<ADTShape, ADTShape::circle> {
    KV(ADTShape::circle);   // Kind Value
    CM(0, ADTShape::center);
    CM(1, ADTShape::radius);
};
\end{lstlisting}

\noindent
\code{KS} specifier within default bindings for \code{ADTShape} tells the library 
that value of a \code{ADTShape::kind} member, extracted from selector at run time, 
should be used to obtain a unique value that identifies the variant. Binding 
definition for \code{circle} variant then uses the same constant 
\code{ADTShape::circle} as the value of the layout parameter of the 
\code{bindings<T,l>} trait and \code{KV(l)} specifier to indicate its \emph{kind 
value}.

Should the shapes have been encoded with a \emph{Tag Class}, the bindings for 
the base class \code{Shape} would have contained \code{KS(Shape::kind)} 
specifier, while derived classes \code{Circle}, \code{Square} and 
\code{Triangle}, representing corresponding variants, would have had 
\code{KV(Shape::circle)} etc. specifiers in their binding definitions. These 
variant classes could have additionally defined a few alternative layouts for 
themselves, in which case the numbers for the layout parameter could have been 
arbitrarily chosen.

\subsection{Views}
\label{sec:view}

Support of multiple bindings through layouts in our library effectively enables 
a facility similar to Wadler's \emph{views}. Reconsider example from 
\textsection\ref{sec:bg} that discusses cartesian and polar representations of 
complex numbers, demonstrating the notion of view. The same example recoded with 
our SELL looks as following:

\begin{lstlisting}
// Introduce layouts
enum { cartesian = default_layout, polar };

// Define bindings with them
template <typename T> struct bindings<std::complex<T>>
    { CM(0,std::real<T>); CM(1,std::imag<T>); };
template <typename T> struct bindings<std::complex<T>, polar>
    { CM(0,std::abs<T>);  CM(1,std::arg<T>); };

// Define views
template <typename T> 
    using Cartesian = view<std::complex<T>>;
template <typename T> 
    using Polar     = view<std::complex<T>, polar>;
...
    std::complex<double> c;
    double a,b,r,f;

    if (match<  complex<double>>(a,b)(c)) // default
    if (match<Cartesian<double>>(a,b)(c)) // same as above
    if (match<    Polar<double>>(r,f)(c)) // view
\end{lstlisting}

\noindent
The C++ standard effectively enforces the standard library to use cartesian 
representation\cite[\textsection26.4-4]{C++0x}. Knowing that, we choose the 
\code{cartesian} layout to be default, with \code{polar} being an alternative 
layout for complex numbers. We then define bindings for each of these layouts as 
well as introduce template aliases for each of the views\footnote{Template 
aliases are analogs of typedefs on parameterized classes}. Template class 
\code{view<T,l>} defined by the library provides a way to bind together a target 
type with one of its layouts into a single type. This type can be used 
everywhere in the library where an original target type was expected, while the  
library will take care of decoding the type and layout from the view and passing 
them along where needed.

The first two match expressions are the same and incur no run-time overhead 
since they use default layout of the underlain type. The third match expression 
will implicitly convert cartesian representation into polar, thus incurring some 
overhead. This overhead would have been present in code that depends on polar 
coordinates anyways, since the user would have had to invoke the corresponding 
functions manually.

\subsection{Solvers}
\label{sec:slv}

This section discusses the user-defined portion of generalized n+k pattern 
semantics outlined in \textsection\ref{sec:semme}. In particular we demonstrate 
how $\Psi_f^\tau$ is defined.

\begin{lstlisting}
@$\Psi_f^\tau:\tau_r\times\tau_1\times...\times1\times...\times\tau_k\rightarrow bool\times\tau$@
\end{lstlisting} 

\section{Implementation} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:impl}

Our implementation of pattern matching expressions follows the naive way of 
essentially interpreting them through backtracking. On one hand, this was a 
consequence of working in a library setting, where code transformations are much 
harder to achive. On the other hand, from the very beginning we were trying to 
find an expressive alternative to object decomposition with either nested 
dynamic casts or visitor design pattern, and thus were not concerned with 
pattern matching on multiple arguments, where decision tree approach becomes 
more efficient. Dealing with single argument certainly leaves less choices for 
optimization, but does not eliminate them as repeated use of constructor-pattern 
with the same target type but different argument patterns essentially leads to 
the same inefficiencies. To tackle this issue in a library setting we rely on 
and give more control to the library user. For example, we fix the order of 
evaluation, but let guard-patterns be placed directly on the arguments of a 
constructor-pattern to let the user benefit from the consciesness of expression, 
while holding a grip on performance. Similarly, we added \code{Alt} sub-clauses 
to \code{Qua}-clause to syntactically separate fast type switching from slow 
sequential evaluation of pattern matching expressions. The fall-through behavior 
of the \code{Match}-statement allows the user to achieve the same effect 
directly with \code{Qua}-clauses, however the performance overhead involved 
justified the addition of otherwise syntactic sugar.

The interpretation of pattern matching expressions with expression templates follows 
very closely the composition of expressions described by abstract syntax 
in~\textsection\ref{sec:syn} as well as their application to selector expression 
described by evaluation rules in \textsection\ref{sec:semme}. This section thus
mainly concentrates on efficient implementation of a match statement as 
well as unification of its syntax to the three encodings of algebraic data types
outlined in \textsection\ref{sec:adt}. The discussion will largely focus on 
devising an efficient \emph{type-switch}, which is then used by our library as a 
backbone to the general match statement presented in~\textsection\ref{sec:semms}. 

Working within a multi-paradigm programming language like C++, we will not be 
just looking at algebraic data types in the closed form they are present in 
functional languages, but rather in an open/extensible form discussed by 
Zenger\cite{Zenger:2001}, Emir\cite{EmirThesis}, L\"oh\cite{LohHinze2006} and others. We will thus 
assume an object-oriented setting where new variants can be added later and form
subtyping relations between each other including those through multiple 
inheritance. We will look separately at polymorphic and tagged class encodings 
as our handling of these two encodings is significantly different. Before we 
look into these differences in greater details, however, we would like to look 
at the problem of type switching without specific implementation in mind as well 
as properties we would like to seek from such an implementation.

\subsection{Unified Syntax}
\label{sec:unisyn}

The discussion in this subsection will be irrelevant for a compiler 
implementation, nevertheless we include it because some of the challenges we 
came accross as well as techniques we used to overcome them might show up in 
other active libraries. The problem is that working in a library setting, the 
toolbox of properties we can automatically infer about user's class hierarchy, 
match statement, clauses in it, etc. is much more limited than the set of 
properties a compiler can infer. On one side such additional information may let 
us generate a better code, but on the other side we understand that it is 
important not to overburden the user's syntax with every bit of information she 
can possibly provide us with to generate a better code. Some examples of 
information we can use to generate a better code even in the library setting 
include:

\begin{itemize}
\item Encoding we are dealing with (\textsection\ref{sec:adt})
\item Shape of the class hierarchy: flat/deep, single/multiple inheritance etc.
\item The amount of clauses in the match statement
\item Presense of Otherwise clause in the match statement
\item Presence of extensions in dynamically linked libraries
\end{itemize}

We try to infer the information when we can, but otherwise resort to a usually 
slower default that will work in all or most of the cases. The major source of 
inefficiency comes from the fact that macro resolution happens before any 
meta-programming techniques can be employed and thus the macros have to generate 
a syntactic structure that can essentially handle all the cases as opposed to 
the exact case. Each of the macros involved in rendering the syntactic structure 
of a match statement (e.g. \code{Match}, \code{Case}, \code{Otherwise}) have a 
version identified with a suffix that is specific to a combination of encoding 
and shape of the class hierarchy. By default the macros are resolved to a 
unified version that infers encoding with a template meta-program, but this 
resolution can be overriden with a configuration flag for a more specific 
version when all the match statements in user's program satisfy the requirements 
of that version. The user can also pin-point specific match statement with the 
most applicable version, but we discourage such use as performance differences 
are not big enough to justify the exposure of details.

To better understand what is going on, consider the following examples. Case 
labels for polymorphic base class encoding can be arbitrary, but preferably 
sequential numbers, while the case labels for tagged class and discriminated 
union encodings are the actual kind values associated with concrete variants.
Discriminated union and tagged class encodings can use both types (views in case
of unions) and kind values to identify the target variant, while polymorphic 
base class encoding can only use types for that. The latter encoding requires 
allocation of a static vtblmap in each match statement, not needed by any other 
encoding, while tagged class encoding on non-flat hierarchy requires the use of 
default label of the generated switch statement as well as a dedicated case 
label distinct from all kind values (\textsection\ref{sec:cotc}). 
When merging these and other requirements into a syntactic structure of a 
unified version capable of handling any encoding we essentially always have to 
reserve the use of default label (and thus not use it to generate 
\code{Otherwise}-clause), allocate an extra dedicated case label, introduce  
a loop over base classes used by tagged class encoding etc. This is a clear 
overhead for handling of a discriminated union encoding whose syntactic 
structure only involves a simple switch over kind values and default label to 
implement \code{Otherwise}. To minimize the effects of this overhead we rely on 
compiler's optimizer to inline calls specific to each encoding and either remove 
branching on conditions that will always be true after inlining or elminate dead 
code on conditions that will always be false after inlining. Luckily for us 
today's compilers do a great job in doing just that, rendering our unified 
version only slightly less efficient than the specialized ones. These 
differences can be best seen in Figure\ref{relperf} under corresponding entries 
of \emph{Unified} and \emph{Specialized} columns.

\subsection{Qualitative Comparison}
\label{sec:qualcmp}

For this experiment we have reimplemented a visitor based C++ pretty printer for 
Pivot's IPR using our pattern matching library. Most of the rewrite was 
performed by sed-like replaces that converted visit methods into respective 
case-clauses. In several cases we had to manually reorder case-clauses to avoid 
redundancy as visit-methods for base classes were typically coming before the 
same for derived, while for pattern matching we needed them to come after. 
Redundancy checking support in the library discussed in \textsection\ref{sec:redun}
was invaluable in finding out all such cases.

During this refactoring we have made several simplifications that became obvious 
in pattern-matching code, but were not in visitors code because of control 
inversion. Simplifications that were applicable to visitors code were eventually 
integrated into visitors code as well to make sure we do not compare 
algorithmically different code. In any case we were making sure that both 
approaches regardless of simplifications were producing byte-to-byte the same 
output as the original pretty printer we started from.

The size of executable for pattern matching approach was smaller than that for 
visitors. So was also the source code. We extracted from both sources the 
functionality that was common to them and placed it in a separate translation 
unit to make sure it does not participate in the comparison. We kept all the 
comments however that were eqaully applicable to code in either approach.

Note that the visitors involved in the pretty printer above did not use 
forwarding: since all the C++ constructs were handled by the printer, every 
visit-method was overriden from those statically possible based on the static 
type of the argument.

%Listing parameter for a case clause always causes access to member. Best hope is 
%that compiler will eliminate it if it is not needed. At the moment we do not 
%have means to detect empty macro arguments or \_.

To be continued...

In general from our rewriting experience we will not recommend rewriting 
existing visitor code with pattern matching for the simple reason that pattern 
matching code will likely follow the structure already set by the visitors. 
Pattern matching was most effective when writing new code, where we could design 
the structure of the code having the pattern matching facility in our toolbox.

\section{Related Work} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:rw}

There are two main approaches to compiling pattern matching code: the first is 
based on \emph{backtracking automata} and was introduced by Augustsson\cite{}, 
the second is based on \emph{decision trees} and is attributed in the literature 
to Dave MacQueen and Gilles Kahn in their implementation of Hope compiler \cite{}.
Backtracking approach usually generates smaller code, while decision tree 
approach produces faster code by ensuring that each primitive test is only 
performed once. Neither of the approaches addresses specifically type patterns 
or type switching and simply assumes presence of a primitive operation capable 
of performing type tests.

Memoization device we proposed is not specifically concerned with compiling 
pattern matching and can be used independently. In particular it can be combined 
with either backtracking or decision tree approaches to avoid subsequent 
decisions on datum that has already been seen.

%xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

\emph{Extensible Visitors with Default Cases}\cite[\textsection 
4.2]{Zenger:2001} attempt to solve the extensibility problem of visitors, 
however the solution, after 
remapping it onto C++, has problems of its own. The visitation interface 
hierarchy can easily be grown linearly (adding new cases for the new classes in 
the original hierarchy each time), but independent extensions by different  
authorities require developer's intervention to unify them all, before they can 
be used together. This may not be feasible in environments that use dynamic 
linking. To avoid writing even more boilerplate code in new visitors, the 
solution would require usage of virtual inheritance, which typically has 
an overhead of extra memory dereferencing. On top of the double dispatch already 
present in the visitor pattern, the solution will incur two additional virtual 
calls and a dynamic cast for each level of visitor extension. Additional double 
dispatch is incurred by forwarding of default handling from base visitor to a 
derived one, while the dynamic cast is required for safety and can be replaced 
with a static case when visitation interface is guaranteed to be grown linearly 
(extended by one authority only). Yet another virtual call is required to be 
able to forward computations to subcomponents on tree-like structures to the 
most derived visitor. This last function lets one avoid the necessity of using 
heap to allocate a temporary visitor through the \emph{Factory Design 
Pattern}\cite{DesignPatterns1993} used in \emph{Extensible Visitor} solution 
originally proposed by Krishnamurti, Felleisen and Friedman\cite{Krishnamurthi98}.

In order to address expression problem in Haskell, L\"{o}h and Hinze proposed to 
extend its type system with open data types and open functions\cite{LohHinze2006}.
Their solution allows the user to mark top-level data types and functions as 
open and then provide concrete variants and overloads anywhere in the program. 
The semantics of open extension is given by transformation into a single module, 
where all the definitions are seen in one place. While open data types introduce 
some of the problems that subclassing does in object-oriented languages, the 
problems are simpler. As we discussed before, the object-oriented analog of 
adding new variants is addition of a class that implements a given interface. In 
other words it is a derived class that extends a strictly flat class hierarchy. 
This largely avoids the problem of classes having multiple types and thus the 
problem of type switching on base classes. Another limitation of their approach 
that prevents from calling it a truly open solution is the fact that their 
semantics essentially assumes a whole program view, which excludes any 
extensions via DLLs. As is the case with many other implementations of open 
extensions authors rely on the closed world for efficient implementation: in 
their implementation \emph{data types can only be entirely abstract (not 
allowing pattern matching) or concrete with all constructors with the reason 
being that pattern matching can be compiled more efficiently if the layout of 
the data type is known completely}. The authors also believe that \emph{there 
are no theoretical difficulties in lifting this restriction, but it might imply 
a small performance loss if closed functions pattern match on open data types}. 
Our work addresses exactly this problem, showing that it is not only 
theoretically possible but also practically efficient and in application to a 
broader problem.

Polymorphic variants in OCaml\cite{garrigue-98} allow addition of new variants 
later. They are simpler, however, than object-oriented extensions as they do not 
form subtyping between variants themsevles, but only between combinations of them. 
This makes an impportant distinction between \emph{extensible sum types} like 
polymorphic variants and \emph{extensible hierarhical sum types} like classes.
An important property of extensible sum types is that each value of the 
underlain algebraic data type belongs to exactly one disjoint subset tagged with 
a constructor. The \emph{nominative subtyping} of object-oriented languages does 
not usually have this disjointness making classes effectively have multiple 
types. In particular, the case of disjoint constructors can be seen as a 
degenerated case of a flat class hierarchy among the multitude of possible class 
hierarchies.

Tom is a pattern matching compiler that can be used together with Java, C or 
Eiffel to bring a common pattern matching and term rewriting syntax into the 
languages\cite{Moreau:2003}. It works as a preprocessor that transforms 
syntactic extensions into imperative code in the target language. Tom is quite 
transparent as to the concrete target language used and can potentially be 
extended to other target languages besides the three supported now. In 
particular, it never uses any semantic information of the target language during 
the compilation process and it does not inspect nor modify the source language 
part (their preprocessor is only aware of parenthesis and block delimiters of 
the source language). Tom has a sublanguage called Gom that can be used to 
define algebraic data types in a uniform mannaer, which their preprocessor then 
transforms into conrete definitions in the target language. Alternatively, the 
user can provide mappings to his own data structures that the preprocessor will 
use to generate the code.

In comparison to our approach Tom has much bigger goals. The combination of 
pattern matching, term rewriting and strategies turns Tom into a 
tree-transformation language similar to Stratego/XT, XDuce and others. 
The main accent is made on expressivity and the speed of development, which 
makes one often wonder about the run-time complexity of the generated code.
Tom's approach is also prone to general problems of any preprocessor based 
solution\cite[\textsection 4.3]{SELL}. For example, when several preprocessors 
have to be used together, each independent extension may not be able to 
understand the other's syntax, making it impossible to form a toolchain.
A library approach we follow avoids most of these problems by relying only on a 
standard C++ compiler. It also lets us employ semantics of the language within 
patterns: e.g. our patterns work directly on underlying user-defined data 
structures, largely avoiding abstraction penalties. A tighter integration with 
the language semantics also makes our patterns first-class citizens that can be 
composed and passed to other functions. The approach we take to type switching 
can also be used by Tom's preprocessor to implement type patterns efficiently -- 
similarly to other object-oriented languages, Tom's handling of them is based on 
highly inefficient \code{instanceof} operator and its equivalents in other 
languages.

%An example would be our generalized n+k patterns where we 
%can turn any invertible function even user defined into a pattern.

There has been previous attempts to use pattern matching with the Pivot 
framework that we used to experiment with our library. In his dissertation, 
Pirkelbauer devised a pattern language capable of representing various entities 
in a C++ program. The patterns were then translated with a tool into a set of 
visitors implementing the underlain pattern matching 
semantics\cite{PirkelbauerThesis}. Earlier, Cook et al used expression templates 
to implement a query language for Pivot's Internal Program Representation 
\cite{iql04}. While their work was built around a concrete class hierarchy 
letting them put some semantic knowledge about concrete classes into the 
The principal difference of their work from this work is that 
authors were essentially creating a pattern matcher for a given class hierarchy 
and thus could take the semantics of the entities represented by classes in the 
hierarchy into account. Our approach is parametrized over class hierarchy and 
thus provides a rather lower level pattern-matching functionality that lets one 
simplify work with that hierarchy.  One can think of it as a generalized 
dynamic\_cast. To be continued...

\section{Future Work} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:fw}

The current implementation of our library relies on static variables and global 
state. This will have problems in a multi-threaded environment so the first 
extension we would like to provide is an efficient multi-threaded 
implementation.

Match statement that we presented here deals with only one scrutiny at the 
moment, but we believe that memoization device along with vtable caching 
technique we presented can cope reasonably efficiently with multiple scrutinies. 
Their support will make our library more general by addressing asymmetric 
multiple dispatch.

Containers as described by the standard C++ library do not have the implicit 
recursive structure present in lists, sequences and other recursive data 
structures of functional languages. Viewing them as such with view will likely 
have a significant performance overhead, not usually affordable in the kind of 
applications C++ is used for. We therefore would like to experiment with some 
pattern matching alternatives that will let us work with STL containers 
efficiently yet expressively as in functional languages.

\section{Conclusions} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:cc}

We implemented a pattern-matching library for C++ that closely resembles 
pattern-matching facilities supported by other languages. Our solution is 
non-intrusive and can be retroactively applied to any polymorphic or tagged 
class hierarchy. It also provides a uniform notation to these different 
encodings of algebraic and extensible hierarchical data types in C++.

We generalize n+k patterns to arbitrary operations by letting the user define 
the exact semantics of such patterns. Such approach avoids hardcoding the 
semantics of n+k patterns into the language, which was a controversial point in 
Haskell that resulted in n+k patterns being removed from the language. Instead, 
we let the user choose the semantics that will be most suitable for his 
application, while we take care of the syntactic convenience only.

We used the library to rewrite an existing code that was relying heavily on 
visitor design pattern and discovered that resulting code became much shorter, 
simpler, easier to maintain and comprehend.

We also believe that approaching pattern matching through library is also an 
important step towards having patterns as a first-class citizens in a language.

\bibliographystyle{abbrvnat}
\bibliography{mlpatmat}
\end{document}
